해시맵

문제 링크 https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 문제 풀이 def dfs(n): if n in dict: return dict[n] else: dict[n] = dfs(n // p) + dfs(n // q) return dict[n] n, p, q = map(int, input().split()) dict = {} dict[0] = 1 print(dfs(n)) 딕셔너리를 활용하니 너무 간단하게 풀리는 문제였습니다. n이 딕셔너리 내에 키로 존재하지 않을 경우 재귀를 돌려 dict의 value를 채워나가며 key가 n인 value를 구하면 결과를 도출할 수 있습니다.