1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 문제 요약 무한 수열 A의 N 번째 값 구하기 A0 = 1, Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1) (⌊x⌋는 x를 넘지 않는 가장 큰 정수이다.) 접근 1. 구현 주어진 조건에 대해 구현하기. N 에 대해서 구해야하므로 Top Down 방식이 나을듯 했다. 그리고 max(N) = 10^12 이므로 꽤 많은 연산이 있을 것이고 중복 되는 값이 있을 것이므로 Dynamic Programming으로 구현한다. DP을 위해 배열을 사용해서 메모리를 잡으면 공간복잡도는 O(N)이나 최대값이 4*10^12이므로 메모리 제한을 초과한다. -> 해시(unordered_map)를 사용해서 필요한 값만 저장..