백준 1351. 무한 수열

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

1351번: 무한 수열

 

예제1을 따라가보면 

 

Ai = A⌊i/2⌋ + A⌊i/3⌋

 

A1 = A⌊0⌋ + A⌊0⌋ = 1 + 1 = 2 

A2 = A⌊1⌋ + A⌊0⌋ = 2 + 1 = 3

A3= A⌊1⌋ + A⌊1⌋ = 2 + 2 = 4 

....

A7= A⌊3⌋ + A⌊2⌋ = 4 + 3 = 7 

 

 

N이 최대 10^12 이므로 만약 bottom-up 방식으로 쌓아간다고 치면 O(N)이 걸릴 것이므로 불가능하다.

top-down으로 하면 되는데 문제가 N이 너무 커서 메모이제이션이 그냥 배열로는 불가능하다.

메모이제이션을 배열이 아닌 map 에다가 하면 해결된다.