[오답노트] 백준 #1629 곱셈 (파이썬) : 나머지 연산의 분배법칙

오늘의 한 마디
이건 알고리즘으로 최적화를 하는 게 아니라 정수론으로 최적화하는 거라... 할 말이 없네요
그냥 개념이라도 익히고 넘어갑시다

• Baekjoon 문제 링크
• solved.ac > 문제 > CLASS 4에 수록된 문제입니다.

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입력 1

10 11 12

예제 출력 1

4

• 시간 제한 : 0.5초(추가 시간 없음)
• 메모리 제한 : 128MB

발상

Solution #1

# A ** B % C

import sys

A, B, C = map(int, sys.stdin.readline().rstrip().split())
print(A ** B % C)

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

당연히 시간 초과.

Solution #2

이 문제의 알고리즘 분류는 분할 정복을 이용한 거듭제곱이다.

분할 정복을 이용하여 A**B를 구현한 결과는 다음과 같다.

def fpow(A, B):
	if B == 1:
		return A
	x = fpow(A, B//2)
    return x*x if B%2 == 0 else x*x*A

솔직히 시간 초과가 되는 이유가 나머지 연산이 아니라 제곱 연산이라고 생각했고,

import sys

A, B, C = map(int, sys.stdin.readline().rstrip().split())

def fpow(A, B):
    if B == 1:
        return A
    x = fpow(A, B//2)
    return x**2 if B%2 == 0 else x**2 * A

print(fpow(A, B) % C)

로 제출했으나, 이 풀이 또한 시간 초과였다.

Solution #3

멘붕에 빠졌고,
이 링크의 풀이를 보고 나머지 분배 법칙을 배웠다.

(A*B) % C = (A%C) * (B%C) % C

A와 B를 곱했을 때 수가 무진장 커진다면, 나머지끼리 곱해서 수를 미리 줄여버려도 괜찮다!

나머지 연산을 미리 하지 않고 A**B를 해버린다면 분할 정복을 통해 구했을지라도
B가 정말로 매우 커지면(이 문제에서는 A, B, C는 모두 2,147,483,647 이하의 자연수였다.)
그 값을 가지고 있는 것만으로도 시간이 오래 걸린다는 걸 이해하는 것이 포인트다.

풀이

# A ** B % C

import sys

A, B, C = map(int, sys.stdin.readline().rstrip().split())

def f(A, B, C):
    if B == 1:
        return A % C
    x = f(A, B//2, C)
    return x**2 % C if B%2 == 0 else (x**2 % C) * (A%C) % C

print(f(A, B, C))

지수가 홀수일 때는 위의 나머지 분배 법칙을 이용하여 중첩 계산해주었다.