[백 준/구현] 1629: 곱셈

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

1629번: 곱셈

핵심 아이디어

• 이 문제는 단순하게 풀면 바로 시간초과가 발생합니다. 따라서 분할정복원리를 활용해서 풀어야합니다.

예를 들어, 2^32라면 2를 32번 곱하는 방법도 있지만, (2^16)^2로 해서 풀면 2를 16번 곱한 것을 다시 2번 곱하니 17번의 연산만으로 끝낼 수 있어 시간이 훨씬 적게 듭니다. 이를 계속 해보면 {(2^8)^2}^2 이렇게 풀면 10번만에, [{(2^4)^2}^2]^2 이렇게 풀면 7번만에 끝낼 수 있어 시간이 획기적으로 주는 것입니다.

 

풀이

import sys
input = sys.stdin.readline
a, b, c = map(int, input().split())

def dac(a,b,c):
	if b == 1:
		return a % c
	if b % 2 == 0:
		return (dac(a, b//2,c)**2)%c
	else:
		return ((dac(a,b//2,c)**2)*a)%c

result = dac(a,b,c)
print(result)

분할정복 함수를 구현해서 풀었습니다. 처음에는 어떻게 접근해야하는지 모르겠어서 다른 사람들의 코드를 참고하여 풀었습니다. 

 

참고 블로그:https://my-coding-notes.tistory.com/93

[🥈1 / 백준 1629 / 파이썬] 곱셈