[BOJ] 1323번 숫자 연결하기 문제 - Python

www.acmicpc.net/problem/1323

1323번: 숫자 연결하기

꽤나 오랫동안 틀려놓고 묵혀둔 문제이다.

 

로직은 간단했는데 마무리가 안됐다.

 

주어진 숫자의 길이만큼 10의 제곱을 해서 곱해주고 원래수를 더해주고를 반복해서 모듈러 K로 0이 나오나 안나오나이다.

 

결국 (mod K) 에서 0이 되는 연산 횟수를 찾는 것인데, 불가능한 경우에서 문제가 생긴 듯 하다.

 

N, K = map(int, input().split())
length = len(str(N))

N = N % K

tmp = 0
ten = (10 ** length) % K
answer = 0
while True:
    answer += 1
    tmp = ((ten * tmp) + N) % K
    if tmp == 0:
        break
    elif ((ten * tmp) + N)% K == tmp:
        answer = -1
        break
    elif tmp == N and answer > 1:
        answer = -1
        break

print(answer)

 

기존의 코드를 위와 같다.

 

어차피 전체 결과에 mod K 해줄 거니까 전부 다 미리 K로 나머지 연산을 해뒀다.

 

그렇게 해도 결과는 같다. 이유는 정수론 시간에 배운 것 같은데 기억 안난다.

 

 

저 반복문에서 벗어나지 못하는 경우가 있어서 시간 초과가 계속 났는데,

 

나는 당연히 결과가 나오지 않는다는 것은 한 숫자로 반복되거나 아니면 기존의 수로 돌아오거나 둘 중에 하나라고 생각했다.

 

근데, 일정 연산을 하다가 루프에 빠지는 경우가 있는 것 같다.

 

그래서 K의 범위가 10만이므로, 방문 확인을 하는 리스트를 하나 추가해서 해결했다.

 

N, K = map(int, input().split())
length = len(str(N))

N %= K

now = N
to_next = (10 ** length) % K

answer = 1

visited = [0] * K

while True:
    if now == 0:
        break
    visited[now] = 1

    now = ((now * to_next) + N) % K
    if visited[now]:
        answer = -1
        break
    answer += 1

print(answer)