코딩스토리

https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 본격적인 행렬 제곱 DP를 사용한 문제이다. 피보나치 수를 구하는 문제는 다이나믹 프로그래밍의 전형적인 문제 유형이다. 대부분 DP를 시작하는 사람들은 피보나치 수를 처음 접하면서 시작한다. 이 문제 역시 피보나치 수를 구하는 문제이다. 다른 점은 n 제한 하나이다. 이 문제의 n제한은 "1,000,000,000,000,000,000"이다. 이번에도 이 숫자가 내 통장잔고였으면.. 하지만 이번 건 스케일이 좀 남다르다. 내 통장잔고의 문제가 아니라 몇 년치 국가 예산보다 크지 ..