Development Artist

도입 백준 단계별 풀기에서 분할정복 여덟 번째 문제이다. 풀이 1. n이 매우 크다. - 점화식으로 푸는 DP 방법 = $O(N)$ -> 비추천 - 행렬로 변환한 풀이법(행렬 거듭제곱) - $O(M^3 * logN)$ -> 사용 2.1. 점화식을 행렬로 변환해보자. 2.2. 여기서 f1 과 f2 는 1이다. 그리고 거듭제곱 결과의 2x2 행렬을 a b c d로 치환하면 2.3. $F_{n+2} = a+b$ 이고 $F_{n+1} = c+d$가 된다. 2.4. 이제 $F_{n}$을 구해보자. n에 n-1을 대입한다. 그렇다면 n-1의 거듭제곱을 구하고 2번째 행의 2개 값을 더해주면 된다. 3. 곱셈 연산자 오버로딩을 사용한다. c++에서는 '연산자 오버로딩'을 찾아보면 더 자세한 내용들이 많을 것이다. p..