BOJ #1629 곱셈

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 1629. 곱셈

문제 풀이

제한시간이 0.5초에다가 제곱수가 20억이 넘어간다. 즉, 일반적인 반복문으로는 TLE 에러가 출력될 가능성이 높기 떄문에 최대한 "제곱"이라는 키워드에 맞춰 시간복잡도를 낮춰야 한다. 거듭제곱의 지수는 곱셈이 서로 덧셈으로 바뀌기 때문에 절반씩 나눠가면서 분할정복을 하면 될 것 같다.

python 코드

def solve(a: int, b: int, c: int) -> int:
    if b == 1: # 지수가 1이면 그대로 계산
        return a % c
    tmp = solve(a, b // 2, c) # 제곱수를 2로 나눈 내림값의 값을 미리 계산
    if b % 2 == 0: # 2로 나누어 떨어지면
        return (tmp * tmp) % c # 2로 나눈 내림값의 제곱과 동일하므로 계산
    elif b % 2 == 1: # 1이 남으면
        return (tmp * tmp * a) % c # 내림으로써 버린 값 a를 다시 곱해서 계산
 
a, b, c = map(int, input().split())
print(solve(a, b, c))