[백준/BOJ] gold5 - 1351번 무한 수열 (Python)

▶1351 - 무한수열

▶문제

무한수열 A는 다음과 같다.

• A0 = 1
• Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)

N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

 

▶입력

첫째 줄에 3개의 정수 N, P, Q가 주어진다.

 

▶출력

첫째 줄에 AN을 출력한다.

728x90

▶풀이

dp와 유사한 방식으로 문제를 풀었다.

dp를 list로 하는 것이 아닌, dictionary를 이용해서 문제를 풀어나갔다.

그 이유는, list로 하니 메모리초과가 나서 찾아보니 dictionary로 하면 괜찮다 해서 그렇게 풀었다.

 

그리고 dp처럼 for문을 사용해서 문제를 푸니 이것도 메모리초과가 발생했다.

n이 10^12까지 가능해서 그렇게 나온 것 같아서, dfs를 이용해 필요한 값들만 가지고 와서 풀었다.

그렇게 푸니까 시간초과가 발생하지 않았다.

def dfs(n):
    if n in arr:
        return arr[n]
    else:
        arr[n] = dfs(n // p) + dfs(n // q) 
        return arr[n]

n, p, q = map(int, input().split())
arr = {}
arr[0] = 1

print(dfs(n))