백준 1629번: 곱셈 (S1) - Python 풀이

문제 설명

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

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

입력

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

출력

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

예제 입력 1

10 11 12

예제 출력 1

4

풀이 과정

이 문제의 핵심 아이디어는 지수를 반씩 줄여서 계산한다라는 것입니다.

예를 들어 a^8은 a를 8번 곱한 값으로, (a^4) * (a^4) 과 같고, a^4는 (a^2) * (a^2) 와 같습니다.

a^(2k) = (a^k)^2 성질을 이용해 지수를 절반으로 줄여서 계산하면, 곱하는 값이 양쪽이 같으니까 하나만 구하면 됩니다. 즉, 필요한 곱셈 횟수가 B번에서 log B번으로 줄어듭니다.

정답 코드

# 입력
A, B, C = map(int, input().split())

# 재귀
# 구하고자 하는 값 a^b%c
def recursive(a, b, c):
    # b(거듭제곱 남은 횟수)가 0이 되면 함수 종료
    if b == 0:
        # 곱셈으로 이루어져 있으니까 1을 반환 (a^0 = 1 이기도 함)
        return 1
    # b를 반으로 나눈 몫을 가지고 재귀 호출
    half_power = recursive(a, b//2, c)
    # half_power는 지수가 절반으로 줄어든 결과이기 때문에 제곱한 값에 %c 한 값이 원래 지수
    half_power = half_power * half_power % c
    # b가 짝수(2k)면 half_power 반환
    if b % 2 == 0:
        return half_power
    # b가 홀수(2k+1)면 half_power까지만 하면 지수가 하나 부족해서 a를 한번 더 곱해줘야 함
    else:
        return a * half_power % c

print(recursive(A, B, C))

• 파이썬에서 // 연산자는 정수 나눗셈(Floor Division, 몫 연산자) 입니다.
• 즉, 두 수를 나누고 소수점 이하를 버린 몫만 반환합니다. 이때, 단순히 버리는 게 아니라 내림(floor) 연산을 적용합니다.

이상입니다.