BFS로 어떤 정수의 0과 1로만 이루어진 배수 찾기

4994번: 배수 찾기

 

정수 N이 주어질때, N의 배수 중에 0과 1로만 이루어진 배수 M을 찾는다

 

1보다 큰 M의 길이는 100이 넘지 않아야하고 가능한 경우가 여러가지 있으면 아무거나 찾는다

 

----------------------------------------------------------------------------------------------------------------------------------------

 

100000000000000000000000000000000 해서

 

0인거 하나씩 1로 바꿔보고 11000000000000000000000, 101000000000000000000....

 

근데 하나만 바꾸는게 아니라 문제는 2개 이상 바꿔야할수도 있잖아

 

111000000000000000000....    1001100000000000000.......

 

이러면 어떻게 해야하지

 

의외로 1부터 시작해서 0이나 1을 추가해보면 모든 경우를 찾을 수 있다

 

이게 느낌이 안오면 한번 써보면 그렇다는걸 알 수 있다

 

1

 

10

11

 

100

101

110

111

 

1000

1001

1010

1011

1100

1101

1110

1111

....

 

큐에 1부터 넣어서 위 과정대로 0이나 1씩 추가해서 정수로 만들어서 배수인지 확인해보고

 

배수가 맞으면 반복문 탈출해서 정답 출력

 

아니면 큐에 다시 넣어서 반복

 

from collections import deque
from sys import stdin

while 1:
    
    n = int(stdin.readline())

    if n == 0:
        
        break

    if 1 % n == 0:
        
        print(1)
    
    else:

        queue = deque([['1']])

        answer = -1

        while queue:
            
            m = queue.popleft()

            m.append('0')

            dm = m[:]

            s = ''.join(dm)

            if int(s) % n == 0:
                
                answer = int(s)
                break
            
            else:
                
                queue.append(dm)
            
            m.pop()

            m.append('1')

            dm = m[:]

            s = ''.join(dm)

            if int(s) % n == 0:
                
                answer = int(s)
                break
            
            else:
                
                queue.append(dm)

        print(answer)

 

 

근데 시간이 오래걸리더라고

 

조금 생각해보니까 나머지를 이용하면 더 쉽겠더라

 

1부터 시작해서 뒤에 0과 1을 붙이는것은 확실하겠는데 위처럼 직접 만드는것보다

 

뒤에 0을 붙이는 것은 원래 수에 10배만 하면 되는거고

 

뒤에 1을 붙이는 것은 원래 수에 10배하고 1을 더하면 된다

 

어떤 수가 n의 배수라는 것은 n으로 나눈 나머지가 0이라는 것

 

나머지 연산의 성질에 따라

 

어떤 수를 n으로 나눈 나머지를 r이라고 하고 10을 n으로 나눈 나머지를 r1이라고 한다면

 

1을 n으로 나눈 나머지는 어차피 1일테니까, (만약에 0이라면 이미 1을 출력했어야한다)

 

뒤에 0을 붙인 경우는 (r * r1) % n이 나머지가 될거고

 

뒤에 1을 붙인 경우는 ((r * r1) + 1) % n이 나머지가 될거

 

나머지 연산만 해도 되므로 어떤 수가 다르더라도 나머지가 서로 같은 경우라면 같은 수로 볼 수 있기 때문에

 

나머지 값을 visited로 체크하면 위에서 직접 0을 붙이고 1을 붙이는거와는 다르게 중복으로 계산하는 경우를 줄일 수 있다

 

당연히 원래 수를 출력해야하므로, 큐에는 (원래 수, 나머지)를 넣어가며 하면 될 것

 

from collections import deque
from sys import stdin

while 1:
    
    n = int(stdin.readline())

    if n == 0:
        
        break

    if 1 % n == 0:
        
        print(1)
    
    else:

        queue = deque([(1,1)])

        visited = [0]*n
        visited[1] = 1

        answer = -1

        r1 = 10 % n

        while queue:
            
            m,r = queue.popleft()

            dr = r*r1
            dr %= n

            if dr == 0:
                
                answer = m*10
                break

            if visited[dr] == 0:
                
                visited[dr] = 1
                queue.append((m*10,dr))
            
            dr = r*r1 + 1
            dr %= n

            if dr == 0:
                
                answer = m*10+1
                break
            
            if visited[dr] == 0:
                
                visited[dr] = 1
                queue.append((m*10+1,dr))

        print(answer)

 

이렇게 하면 훨씬 빠름