[백준]1351 무한수열 #dp#dfs

1.풀이

처음에는 0부터 N까지 올라가는 bottom up 방식으로 쉽게 풀려고 했다. 하지만 N의 범위가 최대 10^12 이기 때문에 P,Q와 관계없이 무조건 시간초과 메모리초과다. ​(소스코드1)

​

올바른 풀이는 다음과 같다. (소스코드2)

(1) top down방식으로 dp를 풀어야 한다. N에서 시작하여 P,Q로 쪼개가면서 탐색한다.

(2) 이때 한번 탐색한 곳은 저장해놓는다 (dp)

(3) 하지만 N의 범위가 10^12 이기 때문에 배열로는 메모리 초과가 난다. 따라서 dictionary 자료형을 써야한다.

새로운 유형의 dp였다.

​

2. 소스코드1

(1) 소스코드1 (bottom up, 메모리초과, 시간초과)

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

dp=[1 for i in range(N+1)]

for i in range(1,N+1):
    a=i//P
    b=i//Q
    dp[i]=dp[a]+dp[b]

print(dp[N])

 

(2) 소스코드2 (top down)

N,P,Q=map(int,input().split())
dp={0:1}
def dfs(n):
    if n in dp:
        return dp[n]
    else:
        dp[n]=dfs(n//P)+dfs(n//Q)
        return dp[n]
print(dfs(N))