[BOJ 1323] 숫자 연결하기

문제 링크 : https://www.acmicpc.net/problem/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을 출력한다.

제한

시간 제한	메모리 제한
2sec	128MB

---

풀이

이 문제는 숫자 $N$을 계속해서 이어 붙여 만든 거대한 숫자가 $K$로 나누어떨어지는 최소의 횟수를 구하는 문제이다. 입력으로 주어지는 $N$은 최대 $1\,000\,000\,000$이고 $K$는 최대 $100\,000$으로, 실제로 숫자를 문자열처럼 이어 붙이면 자료형의 범위를 순식간에 초과하게 된다. 따라서 나머지 연산의 성질을 이용하여 각 단계의 나머지만 계산하는 방식으로 접근해야 한다.

핵심 로직은 다음과 같다:

• 자릿수 계산: $N$을 뒤에 붙인다는 것은 기존 숫자에 $10^{\text{length of } N}$을 곱한 뒤 $N$을 더하는 것과 같다. 예를 들어 $N=10$일 때 $10$ 다음에 $10$을 붙여 $1010$을 만드는 과정은 $10 \times 10^2 + 10$이다.
• 나머지 점화식: 이전 단계의 나머지를 $R_{m}$이라 할 때, 다음 단계의 나머지 $R_{m+1}$은 $(R_{m} \times 10^{\text{length of } N} + N) \pmod K$로 계산할 수 있다.
• 종료 조건 및 불가능 판별: $R_{m} = 0$이 되면 $K$로 나누어떨어지는 것이므로 그때의 횟수를 출력한다. 만약 아무리 반복해도 $0$이 나오지 않는다면, 비둘기집 원리에 의해 나머지의 종류는 최대 $K$가지를 넘을 수 없다. 따라서 $\max(K)$번 이상 반복했는데도 $0$이 나오지 않는다면 같은 나머지가 반복되는 사이클에 빠진 것이므로 $-1$을 출력한다.

이 알고리즘을 사용하면 $O(K)$의 시간 복잡도로 충분히 제한 시간 내에 정답을 도출할 수 있다.

소스코드

Github Link : Source Code

참고 알고리즘 : 비둘기집 원리