라떼는말이야

문제 무한 수열 A는 다음과 같다. A0 = 1 Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1) N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 3개의 정수 N, P, Q가 주어진다. 출력 첫째 줄에 AN을 출력한다. 제한 예제 나의 풀이 이 문제는 메모리 제한이 상당히 빡빡하게 느껴졌다. 기존에 했던 DP 방식대로 메모이제이션(기록하면서 푸는 기법)하기 위해 리스트를 만들어서 문제를 풀이하려고 했다. 사실 메모리 제한에 걸리지 않았다면 절대 어렵지 않은 문제였다. 메모리 초과는 N + 1 크기로 만드는데 리스트를 만들었을 때 최대 크기가 10 ^ 12 + 1 이 된다. 아마 여기서 문제 풀이를 하기도 전에 리스트만 생성하고 메모리가 초과된 것이 아닌가 싶어서 리스트..