문제

0과 1로만 이루어진 N의 배수를 찾는 프로그램을 작성하시오.

풀이

BFS를 사용하여 0과 1로 이루어진 수를 만들어가며 N의 배수를 찾는다.

코드

from collections import deque

def bfs(n):
    q = deque([1])
    while q:
        cur = q.popleft()
        for n_num in (cur * 10 + 0, cur * 10 + 1):
            if len(str(n_num)) > 100:
                continue
            
            if n_num % n == 0:
                return n_num
            q.append(n_num)

while True:
    n = int(input())
    if n == 0:
        break

    print(bfs(n))

시간 복잡도

O(2^100) (worst case, but pruned by modulo check)