백준 1629 곱셈

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

 

 이 문제는 A,B,C가 주어지고 A의 B승을 C로 나눈 나머지를 구하는 문제이다.

 

 이 문제는 A,B,C가 매우 큰 수가 나오므로 통상적으로 거듭제곱을 한다면, 시간복잡도가 O(n)이므로 시간초과가 뜨게 된다. 또한 정수형의 범위도 초과할 수 있으므로 여기서는 분할정복 알고리즘을 응용해야 한다. 필자는 분할정복 알고리즘을 처음 써보기에, https://hbj0209.tistory.com/43 이 블로그를 참고하여 코드를 짰다.

 

 분할정복 알고리즘이란, 복잡한 문제들을 간단한 문제로 쪼개고 쪼개서 간단한 문제 여러 개를 푼 다음 그것을 다시 합쳐서 문제를 해결하는 알고리즘이다. 

이러한 분할정복 알고리즘은 기본적으로 아래와 같은 방식으로 짜여진다

def func(x) :
	if 문제가 간단:
    	return 계산값
	else 문제가 안 간단:
    	x를 x1 , x2로 분할
        retrun func(x1),func(x2)를 합친 값

 

 그렇다면 지금 푸는 이 문제에서 분할정복 알고리즘을 어떻게 쓸 수 있을까? 거듭제곱이란 결국은 같은 숫자를 계속 곱한다는 것이다. 그러므로 곱해야 할 값을 반으로 쪼개서 따로 처리한다면 더 간단해질 수 있을 것이다. 이렇게 쪼개다 쪼개다 승수가 1이 되면 그대로 리턴하면 될 것이다. 또한 우리는 나머지를 구하는 것이므로 구한느 값을 게속 나머지로 만들어 하면 된다. 거듭제곱의 나머지란 결국 하나하나 숫자의 나머지를 다 곱한것의 나머지와 같은 마련이기 때문이다.

 

def fpow(C,n,r):
    if n==1:
        return C%r
    else:
        x=fpow(C,n//2,r)
        if n%2 == 0:
            return x*x%r
        else:
            return x*x*C%r


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

print(fpow(A,B,C))