[백준] 1351번 - 무한 수열 (C++) 문제 및 풀이

문제) 백준 - 동적 계획법(Dynamic Programming) - 무한 수열

-> https://www.acmicpc.net/problem/1351

1351번: 무한 수열

 

 

친절(?)하게도 점화식이 주어졌다. N의 범위가 10^12까지이므로 배열로 memoization 하는 것은 불가능하다. 또한 N이 P와 Q로 계속 나누어지기 때문에 10^12까지 인덱싱 하는 것은 비효율적이다. 따라서 map을 이용하여 memoization을 통해 기존 Top-down 방식의 Dp를 구현했다.

 

 

C++ 소스코드)