4994. 배수 찾기

업데이트 시간 : 2023-07-11 00:13:08 +0000

[Gold III] 배수 찾기 - 4994

문제 링크

성능 요약

메모리: 237264 KB, 시간: 504 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 수학

문제 설명

양의 정수 n이 주어졌을 때, n의 배수 중에서 0과 1로만 이루어진 m을 찾는 프로그램을 작성하시오. n은 200을 넘지 않고, m은 0보다 큰 양의 정수이며, 100자리를 넘지 않아야 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄에는 n (1 ≤ n ≤ 200)이 주어진다. 입력의 마지막 줄에는 0이 주어진다.

출력

입력으로 주어지는 각각의 n마다 m을 출력한다. m의 길이는 100을 넘지 않으며, 가능한 경우가 여러 가지라면 아무거나 출력한다.

💡 Solutions

📄 배수 찾기.py

import sys
from collections import deque
Ns = list(map(int,sys.stdin.readlines()))[:-1]



def solve(N):
    bins = ['1','0']
    que = deque(bins)
    ans = []
    
    while que:
        now = que.popleft()

        for b in bins:
            next_ = b + now
            if int(next_) and int(next_) % N == 0:
                return next_
            else:
                que.append(next_)
    return

for N in Ns:
    x = solve(N)
    print(x)