[백준] 1351 무한 수열 (파이썬 python)

 

 

문제 링크

 

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

1351번: 무한 수열

 

 

문제 풀이

 

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를 구하면 결과를 도출할 수 있습니다.