나머지 연산 - 백준 4375번 [Python]

문제에서 "정답을 ~~~로 나눈 나머지를 출력하라 (경우의 수를 구하는 문제)" 라는 말이 있는 경우 정답이 int나 long long과 같은 저료형의 범위를 넘어가기 때문이다.

따라서 나머지 연산을 통해 해결하면 된다.

 

특히, Python의 경우 정수의 크기 제한이 없지만 2^31-1이 넘어간다면 속도의 문제(O(수의 길이))가 발생하기 때문에 나머지 연산을 통해 해결한다.

 

Example)

https://www.acmicpc.net/problem/4375

4375번: 1

문제 해석)

1로만 이루어진 N의 배수를 찾는다 > 1%N, 11%N, 111%N ... 수 중에서 길이가 최소인 값을 찾는 문제.

이때, 111... 로 나누어 주는데 이때 1로만 이루어진 숫자의 길이가 매우 커질 수 있다.

 

따라서 "N의 배수는 N을 나눈 나머지가 0이다." 라는 컨셉을 가져와 해결한다. 이때, 커질 수 있는 수(11, 111, ...) 만 나머지로 유지하고 나머지는 그냥 연산하도록 둔다.

예를들어, 111%7 은 (11*10 + 1)%7과 같다. 이것을 풀어서 쓰면 (11%7)*10 + 1가 된다. 이를 응용하여 정리하자면,

그리고 이때, N으로 나눈 나머지는 [0,N) 범위 안에 있기 때문에, 최대 N번 반복하면 문제의 정답을 찾을 수 있다.

 

정답)

while True:
    try:
        n = int(input())
    except:
        break
    num = 0
    i = 1
    
    while True:
        num = num*10 + 1
        num %= n
        if num == 0:
            print(i)
            break
        i+=1