BOJ (0과1) 8111

작성일 | In

0과 1

  • 자연수 N이 주어졌을 때, N의 배수 중에서 다음 조건을 만족하는 수를 찾는 문제 (N<=20000)
  1. 0과 1로만 이루어져 있다
  2. 1이 적어도 하나 있다
  3. 수의 길이 100이하이다
  4. 수가 0으로 시작하지 않는다.
  • 아무거나 찾으면 되는데 왜 최소 ?
  • 최소도 사실 아무거나에 해당된다.

  • 아무거나 찾기 위해서 최소를 찾을 건데, 수의 길이를 최소로 만들어볼거다.

  • 첫 번째 수는 무조건 일이다.
  • 1이 적어도 하나 있는거다.
  • 그 뒤로 10,11,100,101,110,111 이런 식으로 계쏙 붙어보면 된다.
  • 총 2^100까지 나온다.

  • 좋은 방법?

  • N의 배수란 점.
  • N의 배수란 조건이 있다면, 나올 수 있는 수의 개수가 N개로 줄어들게 된다.
  • 나머지 연산을 이용해주면 된다.
  • N으로 나누어 떨어져야 한다.
  • (A x B) mod C = (A mod C X B moc C ) mod C
  • 342 는 3x100+4x10+2
  • 는 ((3x10)+4)x(10+2)
  • 이 모든 연산을 수행할 때마다 %N을 해주면 된다.
from collections import deque
t = int(input())
for _ in range(t):
    n = int(input())
    via = [-1]*n
    how = [-1]*n
    dist = [-1]*n
    q = deque()
    q.append(1%n) # 1도 n으로 나눈 나머지를 알아야 한다 n>1이면 이 결과는 항상 1인데, n이 1인 경우에는 0이기 때문에
    dist[1%n] = 0
    how[1%n] = 1
    while q:
        now = q.popleft()
        for i in [0,1]:
            next = (now*10+i)%n
            if dist[next] == -1:
                dist[next] = dist[now] + 1
                via[next] = now
                how[next] = i
                q.append(next)
    if dist[0] == -1:
        print('BRAK')
    else:
        ans = ''
        i = 0
        while i != -1:
            ans += str(how[i])
            i = via[i]
        print(ans[::-1])

참고자료 codeplus

0%