티스토리 뷰

728x90

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

 

1351번: 무한 수열

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

www.acmicpc.net

 

문제에서 기본 알고리즘은 주어지므로 재귀나 반복문으로 구현하면 해결할 수 있지만 list로 구현할 시,

시간 복잡도나 공간 복잡도를 만족하지 못하는 상황이 발생합니다.

이런 이유로 dict() 자료구조로 구현해야 메모리나 시간 복잡도를 문제를 해결 가능합니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys
from collections import defaultdict
 
 
def dp(n):
    if lst[n] != 0:
        return lst[n]
    lst[n] = dp(n//P) + dp(n//Q)
    return lst[n]
 
 
if __name__ == "__main__":
    std = sys.stdin.readline()
    N, P, Q = map(int, std.split())
    lst = defaultdict(int)
    lst[0= 1
    print(dp(N))
cs

 

댓글