[baekjoon] 백준 1629번(파이썬): 곱셈

문제

1629번: 곱셈

알고리즘

- 시간 초과가 나오지 않게 하기 위해 재귀적으로 탐색한다.

- 재귀적으로 탐색할 때 현재 수를 1번 곱해도 되는 거라면 현재 값을 c로 나눈 나머지를 리턴한다.

- 곱해야 하는 수가 1보다 크다면 현재 수와  b//2로 나눈 값을 재귀적으로 탐색시킨다.

- 탐색이 끝나고 나면 b가 짝수인지 홀수인지 확인한다.

- 짝수라면 탐색이 끝난 후 리턴 받은 수를 2번 곱하고 c로 나눈 나머지 값을 리턴한다.

- 홀수라면 탐색이 끝난 후 리턴 받은 수를 2번 곱하고 a를 한번 더 곱한 후 c로 나눈 나머지 값을 리턴한다.

코드

import sys


# 거듭제곱을 재귀적으로 수행
def fpow(a, b):
    # 1번 곱해도 되면 a % C를 리턴
    if b == 1:
        return a % C

    # 곱해야하는 수가 1보다 많다면
    else:
        # 곱해야하는 수를 반으로 나누어 재귀적으로 탐색
        x = fpow(a, b//2)

        # 곱해야하는 수가 짝수이면
        if b % 2 == 0:
            return x * x % C

        # 곱해야하는 수가 홀수이면
        else:
            return x * x * a % C


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

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법