[분할정복/재귀] 백준 1629 곱셈 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1629번: 곱셈

 

 

 

2. 문제 풀이

 효율적으로 거듭제곱을 구하는 문제입니다. 단순히 A**B를 하면 시간 초과가 납니다.

 

2022.01.29 - [Algorithm] - [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘

[Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘

 재귀함수를 이용한 분할정복으로 풀어야 합니다. A^B를 A가 될 때까지 계속 둘로 나누다가, A가 되면 거슬러 올라오면서 곱하면 됩니다.

 

1) Divide: A^B가 A가 될 때까지 2분할
2) Conquer: 둘로 나눈 A의 제곱 % C 
3) Combine: 나눴던 둘을 다시 곱함

 

 

 

3. 코드

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

# 분할정복
def power(a, b):
    if b == 1:  # b의 값이 1이 될 때까지 재귀
        return a % C
    else:
        tmp = power(a, b // 2)  # a^(b // 2)
        if b % 2 == 0:
            return tmp * tmp % C  # b가 짝수인 경우
        else:
            return tmp * tmp * a % C  # b가 홀수인 경우

res = power(A, B)
print(res)

 둘로 나눌 때, b가 홀수 or 짝수인지 체크해야 합니다.

 만약 홀수라면, a를 따로 곱해줘서 맞춰줍니다.