[파이썬] 백준 1354번 - 무한 수열 2 풀이

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

티어: 골드 5

로직

 

수열 A의 모든 값을 구할 필요가 없으므로 탑다운 방식을 사용합니다.

수열 A는 dp 변수에 딕셔너리 형태로 저장하며, 초기값으로 A[0] = 1이 되도록 설정해줍니다.

 

수열 A의 i번째 값을 구하는 A(i)라는 함수를 만들어봅시다.

맨 처음, dp[i]값이 이미 저장되어 있는지 확인하고, 저장되어 있다면 그 값을 반환합니다.

A[i]에서 i가 0 이하의 값이라면 1이므로 i의 를 max(0, i)로 설정해줍니다.

 

A(i//p - x)와 A(i//q - y)의 값을 재귀적으로 구하고, 둘을 더한 값을 dp[i]에 저장하고 반환합니다.

구하고, 둘을 더한 값을 dp[i]에 저장하고 반환합니다.