[Python] 33756번 88888

https://www.acmicpc.net/problem/33756

---

 

25/04/05

 

 

실버 문제인데 재밌다고 느꼈던 문제라서 소개하고자 한다.

---

 

문제 접근 방식:

 

 

모든 자리수가 8인 수를 8-넘버라고 할 때, 어떤 수 $N$이 8개 이하의 8-넘버의 합으로 표현될 수 있는가를 물어보는 문제이다.

 

좀 생각하다가, 실버 3치고는 살짝 어려운데? 라고 생각이 들 때쯤 쉽게 아이디어가 떠올랐다.

 

생각을 해보면 모든 자리수가 8인 수는 모든 자리수가 1인 수 $\times$ 8 의 형태를 가지고 있다.

 

즉, 8의 배수라는 소리고, 8의 배수끼리 더해도 8의 배수이기 때문에, 일단 $N$은 8의 배수여야만 할 것이다.

 

$N$이 8의 배수라면, 8로 나눠보자.

 

그러면 나눈 수가 모든 자리수가 1인 수들의 합으로 표현되어야 할 텐데, 그건 판별하기 매우 쉽다.

 

그 수가 오름차순의 형태를 가지고 있으면 된다!

 

예를 들자면, $11111+111+1 = 11223$이 된다. 이런 예시를 하나 생각해보면 오름차순이어야 함을 금방 알 수 있다.

 

또한, 나눈 수에 $9$가 존재한다면 8개를 더한게 아니라 9개 이상을 더한 것이므로 불가능한 것이라고 판별할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    if N % 8 != 0:
        print('No')
    else:
        A = N//8
        A = str(A)
        B = list(A)
        B.sort()
        B = ''.join(B)
        if '9' in A:
            print('No')
        elif B != A:
            print('No')
        else:
            print('Yes')