https://www.acmicpc.net/problem/10830 <풀이> 우선 B의 최대값이 100,000,000,000 (100억) 이다. 1초안에 통과시키려면 O(n) = 10^8이 되어야하는데 턱없이 부족하다. 그래서 최소 O(logN)으로 풀어야겠다고 생각했고, 아는 게 이분탐색밖에 없으니 이분탐색으로 접근을 했다.
이분탐색에서 가장 중요한 건 다음 재귀호출에서 Search Space를 절반으로 줄이는 것이다. 예를 들어, B가 4인 경우에는 총 4번 계산해야 할 것을 " O(log4) = 2"를 이용하여 두 번만에 계산할 수 있다.
각 depth마다 우측 자식노드는 좌측 자식노드와 동일하므로 "재활용"한다고 생각하면 Search Space를 절반으로 줄여갈 수 있..........
원문 링크 : boj_10830_행렬제곱
