[python] 백준 1629번 - 곱셈

1629번: 곱셈 (acmicpc.net)

1629번: 곱셈

 

문제 자체는 어렵지 않았다. 물론 이해하는 데만 어렵지 않았다.

분할정복을 이용해 풀어야 했기 때문에 대체 어떻게 접근해야 하는 것인지 모르겠어서

애를 먹었고

결국 다른 풀이를 참고하여 이해할 수 있었다.

지수법칙만 알면 간단하게 풀 수 있다.

 

문제의 예제인 [10, 11, 12]를 예로 들자면

10**11%12는 10**5*10**6%12와 같이 나눌 수 있다.

마찬가지로 계속해서 지수법칙을 사용하여 나누면 계산해야 할 횟수가 줄어든다.

 

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

def solution(a,b):
    if b ==1:
        return a%c  
    else:
        tmp = solution(a,b//2)	
        if b%2 == 0:			# 지수가 짝수일 때와 홀수일 때를 나누어 생각
            return tmp*tmp%c  
        else:
            return tmp*tmp*a%c
        

print(solution(a,b))