백준 1629번 Python / Math

문제 링크

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

1629번: 곱셈

 

시간 초과 풀이

a,b,c = map(int, input().split())
remainder = []
cal = a

while True:
    tmp = cal % c
    if not tmp in remainder:
        remainder.append(cal % c)
        cal *= a
    else: break

answer = remainder[b % len(remainder)]
print(answer)

거듭제곱을 순차적으로 진행하면서, 나머지를 구합니다.

리스트에 해당 거듭제곱 결괏값의 나머지가 없으면 추가해주고 이미 존재하는 값이 나온다면 반복문을 중지합니다.

나머지가 들어있는 리스트의 길이와 b를 나눈 나머지가 인덱스 값이 되고,

정답은 계산한 인덱스를 나머지가 들어있는 리스트에 적용해 뽑아오는 방식입니다.

당연히, 시간 초과가 나왔습니다 ㅠㅠ..

 

런타임 에러 풀이

import math

a,b,c = map(int, input().split())
remainder = []

for i in range(1, b+1):
    tmp = math.pow(a,i) % c
    if tmp not in remainder:
        remainder.append(int(tmp))
    else : break

answer = remainder[b % len(remainder)]
print(answer)

위 코드는 런타임 에러(overflow)발생 코드입니다.

위의 코드와 같은 방식으로 진행했습니다.

앞선 코드에서 시간 초과가 나왔기 때문에 math 라이브러리를 이용해 거듭제곱을 구하고자 생각했습니다.

math 라이브러리의 pow() 함수를 사용한다면 쉽게 거듭제곱을 구할 수 있기 때문에 적용을 해보았으나,

문제에서 제시하는 a, b, c의 range가 매우 커서 연속해서 overflow에러가 발생했습니다.

 

정답 풀이

a,b,c = map(int, input().split())

def multi(a, b):
    if b == 1:
        return a % c
    else:
        tmp = multi(a, b//2)
        if b % 2 == 0:
            return tmp * tmp % c
        else:
            return tmp * tmp * a % c

print(multi(a, b))

전혀 감이 잡히질 않아서 오랜 시간 고민 끝에 구글링을 통해 해결책을 찾았습니다.

핵심은 지수 법칙과 나머지 분배 법칙을 적용시키는 것이었습니다.

지수 법칙 : \(A^{m+n} = A^{m}*A^{n}\)

나머지 분배 법칙 :  (A x B) % C = (A % C) x (B % C) % C

해당 수학 법칙들을 적용하여,

b가 1일 때는 바로 계산해주고,

b가 짝수이면 10^10 -> (10^5)^2 형태로 바꿔주며,

b가 홀수이면 10^10 -> (10^5)^2 * 10의 형태로 바꿔주는 방식입니다.