BOJ 1354번(무한 수열2)

난이도

---

골드 V

 

 

풀이

---

처음 풀이에서는 메모이제이션으로 안 풀고 재귀만 돌려서 시간 초과가 났고,

 

두번째 풀이에서는 맵이 아닌 리스트를 활용해서 리스트에 N+1 크기만큼을 미리 만들어두어서 메모리 초과가 났다.

 

세번째 풀이에서는 리스트가 아닌 맵으로 풀었더니 통과했다

-> 탐색해보면 모든 수를 다 따지는 것이 아니다. 따라서 리스트 보다는 맵을 사용하는 것이 더 적절한 것 같다.

 

import sys

input=sys.stdin.readline

checkmap = {}

N,P,Q,X,Y=map(int,input().split())

def get(n):
    if n<=0:
        return 1
    elif n in checkmap:
        return checkmap[n]
    else:
        checkmap[n]=get(n//P-X)+get(n//Q-Y)
        return checkmap[n]

print(get(N))

 

 

링크

---

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

1354번: 무한 수열 2