[BOJ] 백준 1629 곱셈 (Swift)

문제

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

1629번: 곱셈

풀이

단순히 21억번 제곱하게 된다면 ($O(n)$) 시간내에 해결할 수 없습니다.

문제 예제와 같이 $10^{11}$ 을 구한다고 가정해보겠습니다.
단순히 11 제곱을 구하면 11번의 연산이 필요하겠죠?

분할 정복 알고리즘을 사용해 $O(log_n)$ 의 시간복잡도를 갖도록 동작할 수 있습니다.

$10^{11} = 10 * 10^{10}$ 이고, $10^{10} = 10^5 * 10^5$ 가 되겠죠?
$10^5 = 10 * 10^4$ 이고, $10^4 = 10^2 * 10^2$, $10^2 = 10 * 10$ ...

이런 방식으로 $10^{11}$ 을 구해줄 수 있습니다.

11제곱을 구하기 위해 10제곱이 필요 -> 5제곱 필요 -> 4제곱 필요 -> 제곱 필요 -> 10
가 됩니다. 짝수일 때, 반씩 줄여나가므로 $O(log_n)$의 시간복잡도를 가지고 구할 수 있습니다.

코드를 참고하시면 이해하는데 도움이 될 것입니다.

소스코드

후기

분할 정복을 사용해 거듭제곱을 구할 수 있다는 점이 재밌었습니다.