[백준-파이썬] 1323: 숫자 연결하기

문제 보러 가기!!

와아... 많은 시간 초과를 겪은 끝에 드디어 맞았다. 🤣🤣

아이디어 ⭐

N이 K로 나눠지는지 본다. -> N을 두 번 써서 K로 나눠지는지 본다. -> 쭉 본다.
K로 나눠지면(나머지가 0이면) 그만두고, N을 몇 번 썼는지 출력한다.

불가능한지 판단하는 기준은 ??
나머지를 쭉 저장한다. -> 나왔던 나머지가 또 나오면, 그 패턴이 반복된다는 거니까 불가능하다고 본다. (이걸 증명하는 수학적인 개념은 모르겠는데, 찾아봐야겠다.)

N을 n번 쓸 때 모듈러 연산을 활용했다 !! 나도 처음 알게 된 것이라서, 기억할 겸 쓴다. 모듈러 연산의 모듈러는 modulo 즉 나머지이다. 나머지를 구할 때 사용할 수 있는 세 가지 성질이 있다.

1. (A+B) % C = (A%C + B%C) % C
2. (A-B) % C = (A%C - B%C) % C
3. (AXB) % C = (A%C X B%C) % C

이를 활용했다.

코드 👩‍💻

일단 내 풀이 코드를 보겠다.

input = sys.stdin.readline

N, K = map(int, input().split())
num = N % K
cnt = 1
N_len = len(str(N))
jarisu = 10 ** N_len

already = set()

while True:
    # print(num)
    if num == 0:
        break


    else:
        num = (N % K + (num * (jarisu % K)) % K) % K

        cnt += 1
        if num in already:
            cnt = -1
            break

        already.add(num)

print(cnt)

모듈러 연산을 적용한 부분

num = (N % K + (num * (jarisu % K)) % K) % K 부분에서 모듈러 연산을 적용했다.
num은 N을 cnt번 적었을 때의 나머지이다.

N을 cnt번 적으려면 어떻게 해야 할까?
N이 100이라면..
100 -> 100100 -> 100100100 ... 이런 식으로 적어야 할 것이다.

각각의 나머지는 100 % K -> 100100 % K -> 100100100 % K .. 이런 식으로 될 것이다.

모듈러 연산을 쓰면 각각의 나머지를 아래처럼 나타낼 수 있다.
100 % K -> (100 % K + 100000 % K) % K -> (100 % K + 100100000 % K) % K
즉 이번 수의 나머지 = (N % K + (이전의 수에 N자릿수만큼 0 붙인 것 % K)) % K 으로 나타낼 수 있다.
이 부분을 정리하면 num = (N % K + (num * (jarisu % K)) % K) % K가 된다.

(이전의 수에 N자릿수만큼 0 붙인 것 % K)
이전 수에 N 자릿수만큼 0을 붙이려면, 이전 수 X (10^(N자릿수 * cnt))를 해야 한다.

=> (이전 수 X (10^(N자릿수 * cnt))) % K
(10^(N자릿수 * cnt))부분은 10 ^ (N자릿수 * (cnt-1)) X 10 ^ (N자릿수)로 바꿀 수 있다. 10^3 = 10 ^ 2 X 10 으로 바꾸는 것처럼 !

=>((이전 수 X 10 ^ (N자릿수 * (cnt-1))) X 10 ^ (N자릿수) ) % K = ((이전 수 X 10 ^ (N자릿수 * (cnt-1))) % K X 10 ^ (N자릿수) ) % K ) % K
(이전 수 X 10 ^ (N자릿수 * (cnt-1))) % K은 이전 수의 나머지이다. 즉 num이다.

=> (num X (10^(N자릿수))%K) %K

코드에서는 10 ^ (N의 자릿수)를 jarisu로 했다. 그래서 정리하면 num = (N % K + (num * (jarisu % K)) % K) % K가 된 것이다 !!!

추가

아! 그리고 처음에 '맞았습니다.' 받은 코드는 파이썬으로는 실패하고 파이파이로도 2436ms가 걸렸다.
여기에서 리스트를 set으로 바꾸니까 파이썬으로 통과할 수 있었고, 파이파이로는 120ms에 통과했다.