[BOJ] 1629 : 곱셈 [분할정복](Python)

문제 링크

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

1629번: 곱셈

소스 코드

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

def div(a,b,c):
    if b == 1:
        return a % c

    tmp = div(a,b//2,c)

    if b % 2 == 1:
        return tmp**2 * a % c
    else:
        return tmp**2 % c

print(div(a,b,c))

 

해설

• 분할정복, 재귀

문제에 주어진 a,b,c의 범위는 최대 21억으로 일반적인 곱셈 연산을 수행하면 무조건 시간초과가 나게 되어있습니다.

21억을 21억번 곱하면서 21억으로 나눈 나머지를 구한다고 한다면 몇 번의 연산이 필요할까요..?

 

따라서 이 문제는 작은 것으로 쪼개어 각각 풀이하는 분할 정복(Divide and Conquer)으로 접근해야 합니다.

 

위 문제에서는 지수의 합이 밑의 곱셈으로 나눠질 수 있다는 특징을 생각해보면 이해가 잘 됩니다.

$10^{4}=10^{2}\times 10^{2}$

$10^{5}=10^{2}\times 10^{2}\times 10^{1}$

 

따라서 우리는 b번만큼 a를 곱하는 과정에서 b를 쪼개어 작은 숫자들로 만들어주는 것입니다.

b가 1이 될 때까지..!

 

이때 반복적으로 2로 나누게 되는데 나머지가 1이 존재하는 경우, 즉 b가 홀수인 경우에는 두 번째 수식처럼 a를 한 번 더 곱해줘야 합니다.

 

추가로 시간 복잡도가 어떻게 될지에 대해 생각해보면..$2^{35}=34,359,738,368$ 입니다.따라서 재귀 깊이가 최대 35층 정도 될 것임을 짐작할 수 있습니다.