https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 알고리즘 도가뉴 항등식을 이용해서 푸는 분할정복 문제였다. 도가뉴 항등식 $$ F_{m+n} = F_{m-1}F_{n} + F_{m}F_{n+1} $$ 위의 항등식을 활용해 $m+n$이 짝수일 때와 홀수일 때를 나눠서 점화식을 이용해 분할정복을 해준다. 이때 맵을 통해서 불필요한 계산을 방지하기 위해 한 번 계산한 값은 저장해주고 다음에 쓰일 때 바로 맵에서 꺼내 쓰는 다이나믹 프로그래밍도 쓰인다. 모듈러 계산도 중요하다. 소스 코드 #include #define..