[백준] 1323번 - 숫자 연결하기

📩 출처

문제

영훈이는 태형이에게 어떤 수 N과 K를 주었다.

태형이는 N을 종이에 쓰기 시작했다. 태형이는 자신이 이 수를 몇 번 써야 그 수가 K로 나누어지는지 궁금해지기 시작했다.

N=10일 때, 이 수를 한 번 쓰면 10이고, 두 번 쓰면 1010이고, 세 번쓰면 101010이고,... 이런식이다.

어떤 수 N과 K가 주어졌을 때, N을 몇 번 써야 K로 나누어 떨어지는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. K는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 몇 번 써야하는지 그 최솟값을 출력한다. 만약 아무리 써도 불가능할 경우에는 -1을 출력한다.

👉 생각

• 이 문제에서 가장 중요한 점은 하나의 규칙을 찾는 것인데, 규칙은 다음과 같다.
  
• 22를 나누었을 때 나머지가 4인것을 기억하고 있다가, 222를 9로 나누었을 때 앞에 22를 나누고 나머지 4와 마지막 2를 통해 42를 나누게 된다. 즉 n을 옆에 붙여줄 때마다 그 값의 나머지와 새로운 n이 붙게 되어 k로 나누게 되는 것이다.
• 예를들어 n이 101, k = 9이고 cnt가 1일 때는 나머지가 2이다. cnt가 2일 때 n은 101101이고 위의 규칙을 적용하면 2101이 된다.
• 따라서 나머지 tmp와 10 * n의 길이 + n이 새롭게 나누어 줄 값이 n이 된다. 이 값을 계속 나누면서 생기는 나머지를 v에 기록하고, 이전에 나머지와 똑같은 나머지가 발생한다면 영원히 나눌 수 없기 때문에 -1을 출력한다.

n, k = map(int, input().split())

v = [0] * k
x = 10**len(str(n))
cnt = 1
res = n
while True:
    tmp = n % k
    if not tmp:
        print(cnt)
        break
    else:
        if v[tmp]:
            print(-1)
            break
        else:
            cnt += 1
            n = tmp*x + res
            v[tmp] = 1