[백준] 1629 곱셈

J. Hwang·2025년 1월 23일

Coding python 코딩테스트

coding test

목록 보기

86/108

문제

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

입력

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

출력

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

내 풀이

풀이 1

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

def solution(a, b, c):
    if b == 1:
        return a%c
    X = solution(a, b//2, c)
    if b%2==0:
        return X*X%c
    else:
        return a*X*X%c
    
print(solution(a, b, c))

풀이 2

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

코멘트

너무너무 a**b%c 하고 싶었지만 그렇게 곧이 곧대로 풀라고 낸 문제가 아닐 것이다....
그래서 어떻게 해야 더 효율적으로 풀 수 있을지 머리를 싸매고 고민했지만 결국 풀지 못해서 찾아보니 "분할 정복을 이용한 거듭제곱"이라는 개념을 이용해야 하는 것이었다. (알고리즘이라기 보다는 수학적 아이디어가 필요한 문제였다.)
극단적으로 B = 2,147,483,646라고 생각해보자. 그러면 A가 뭐가 되었던 간에 A를 2,147,483,646번 곱해야하는데, 당연히 시간 초과가 뜰 것이다.
"분할 정복을 이용한 거듭제곱" 개념을 활용하면, 이 연산의 횟수를 단번에 절반으로 줄일 수 있다. $A^{2,147,483,646}$ = $(A^{1,073,741,823})^2$ 이므로, 2,147,483,646번의 연산이 (1,073,741,823 +1)번의 연산으로 확 줄어드는 것이다. 한 번 더 생각해보면 $A^{2,147,483,646}$ = $(A^{1,073,741,823})^2$ = $((A^{536,870,911})^2)^2 \times A$ 로 (536,870,911 + 3)번의 연산으로 또 절반으로 줄어든다. 이를 코드로 구현한 것이 풀이 1이다.