[Python] 백준 1351번 : 무한 수열

---

<접근 방법1(Bottom-Up 방식의 DP) - 메모리 초과>

1. 수열의 첫 값도 정해져있고 각 항의 관계도 정의되어 있으므로 그대로 구현하면 되겠다.
2. 결국 A[N]을 구해야하므로 N+1개의 원소를 갖는 lst를 미리 정의해두고 시작하겠다.
3. 마지막 항인 lst[-1]을 출력한다.

# Bottom-Up 방식
N, P, Q = map(int, input().split())
lst = [0]*(N+1)
lst[0] = 1
for i in range(1, N+1):
    lst[i] = lst[i//P] + lst[i//Q]
print(lst[-1])

<접근 방법2(Top-Down 방식)>

1. dictionary에 {0:1}을 넣어두고 만일 저장된 값이 있다면 그대로 사용하고, 저장된 값이 없으면 계산해서 새로 저장하는 구조를 그리면 되겠다.
2. 위와 같이 구현하면 재귀 형태가 들어갈 수 밖에 없을 것이다. 그러나 모든 인덱스에 대한 값을 구할 필요가 없기 때문에 메모리 초과는 걸리지 않게 된다.

# Top-Down 방식
def sol(n):
    if n in dictionary:
        return dictionary[n]
    else:
        dictionary[n] = sol(n//P) + sol(n//Q)
        return dictionary[n]


N, P, Q = map(int, input().split())
dictionary = dict()
dictionary[0] = 1
print(sol(N))
print(dictionary)

 

이해가 되지 않는 부분이 있다면 질문 주세요. 감사합니다.