BaekJoon
[BaekJoon] 11444번 피보나치 수 6 (Java) 문제 풀이 [Gold 2]
문제 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 어떻게 풀 것인가? 처음에 보고 조금 당황스러웠다. DP로 풀기에는 너무나도 큰 수 이다. 아마 처음에 단순 DP로 접근했다면 분명히 시간초과가 발생했을 것이다. 그렇다면 이러한 시간초과 부분을 획기적으로 줄일 수 있는 것이 무엇이 있을까? 바로 행렬이다. 사실 백준알고리즘을 많이 풀어본 이들이라면 위와 같은 피보나치 문제들은 많이 봐왔기 때문에 아래와 같은 점화식은 익숙할 것이다. D(n+2) = D(n+1) + D(n) ( D0 = 0, D1 = 1, n >= 0)..
