[백준_분할정복] 1629번 - 곱셈 - 이해까지 도와주는 풀이

문제

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

 

 

 

입력

 

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

 

 

출력

 

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

 

 

예제 입력

10 11 12

 

 

예제 출력

 

4

 

 

 

풀이

 

이 문제는 지수가 짝수인 경우와 홀수인 경우를 나눠서 풀 수 있습니다.

 

지수가 짝수인 경우

만약 b가 짝수라면, half_power에는 power_mod(a, b //2 , c)를 호출하여 a를 b의 절반으로 제곱한 결과를 저장합니다.

그리고 나서 (half_power * half_power) % c 를 계산하여 a를 b번 곱한 값의 나머지를 구합니다.

여기서 절반 지수를 이용해 지수 연산을 빠르게 수행합니다.

 

예를 들어, 2를 4번 곱한다고 하면 2를 2번 곱한 값을 half_power에 저장합니다. 4겠죠.

그리고 나서 그 값으로 (4 * 4) % c를 계산하여 2를 4번 곱한 값의 나머지를 구하게되는겁니다.

짝수라서 가능한 빠른 방법입니다.

 

 

그럼 홀수인 경우에는 어떻게 해야할까요?

정석대로 a를 b번 다 곱해야합니다. b를 1씩 줄이면서 횟수를 카운트하면되겠죠.

(a * power_mod(a, b - 1, c)) % c를 계산하여 a를 b번 곱한 값의 나머지를 구하면 됩니다.

 

 

소스 코드로 살펴보겠습니다.

 

 

소스코드

 

# 사용자로부터 세 개의 정수 입력을 받아서 a, b, c에 저장합니다.
a, b, c = map(int, input().split())

# 거듭제곱을 계산하고 나머지를 구하는 함수를 정의합니다.
def power_mod(a, b, c):
    # 기저 조건 1: 지수(b)가 0이면 결과는 1입니다.
    if b == 0:
        return 1
    # 지수(b)가 짝수인 경우
    elif b % 2 == 0:
        # a^b를 계산하기 위해 a^(b//2)를 먼저 계산하고 나머지 연산을 수행합니다.
        half_power = power_mod(a, b // 2, c)
        # a^b = (a^(b//2) * a^(b//2)) % c
        return (half_power * half_power) % c
    # 지수(b)가 홀수인 경우
    else:
        # a^b = (a * a^(b-1)) % c
        return (a * power_mod(a, b - 1, c)) % c 

# power_mod 함수를 호출하고 결과를 출력합니다.
print(power_mod(a, b, c))