dictionary와 재귀를 이용한 다이나믹 프로그래밍 기본 테크닉 배우기1

1. 문제

 

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

1351번: 무한 수열

 

주어진 수열의 점화식에서 A[N]을 구하는 문제

 

 

2. 풀이

 

처음에 그냥 이게 문제?하면서 점화식 그대로 작성했는데 메모리 초과남..

 

from sys import stdin

n,p,q = map(int,stdin.readline().split())

dp = [0]*(n+1)

dp[0] = 1

for i in range(1,n+1):
    
    dp[i] = dp[i//p]+dp[i//q]

print(dp[n])

 

n의 최대 범위는 $10^{12}$인데 메모리 제한은 128mb라서 그런 것 같다

 

근데 dp[n]을 구할려면, dp[n//p]와 dp[n//q]를 알면 그만이다

 

그러니까 1부터 n까지 모두 dp에 저장할 필요가 없고 n//p와 n//q중에 더 큰 값까지만 저장하면 조금이라도 줄일 수 있을 것 같았다

 

from sys import stdin

n,p,q = map(int,stdin.readline().split())

max_range = max(n//p,n//q)

dp = [0]*(max_range+1)

dp[0] = 1

for i in range(1,max_range+1):
    
    dp[i] = dp[i//p]+dp[i//q]

print(dp[n//p]+dp[n//q])

 

 

이러니까 60%까지는 가는데 그 이상은 메모리 초과나더라

 

그런데 조금 더 생각해보니까

 

A[n]을 구할려면, A[n//p]를 알아야돼.. 그러면 A[n//p]만 알면 돼

 

그런데 A[n//p]를 구할려면??? 다시 A[n//p] = A[(n//p)//p] + A[(n//p)//q]니까, A[(n//p)//p]를 구해야돼

 

그런데 A[(n//p)//p]를 구할려면..? 다시 A[((n//p)//p)//p]를 알아야돼...

 

즉 A[n]을 구할려면..

 

A[n//p], A[(n//p)//p], A[((n//p)//p)//p],.............

 

A[n//q], A[(n//q)//q], A[((n//q)//q)//q],........... 만 안다면.. A[n]을 구할 수 있어

 

중간에 비어있는 A[1],A[2],...이런거는 구할필요가 없다는거지

 

그런데 A[n//p], A[(n//p)//p], A[((n//p)//p)//p],......... 이거는 자세히 보면...... 재귀로 구할 수 있을 것 같네

 

f(i)에서 f(i//p)를 재귀호출하면 구할 수 있을 것 같아

 

-----------------------------------------------------------------------------------------------------------------------------

 

메모리를 최대한 아끼기 위해 dictionary를 이용하고

 

만약에 A[i]를 이미 구했다면, dp[i]를 return하지만

 

구하지 않았다면, dp[i] = dfs(i//p) + dfs(i//q)로 재귀호출해서 구하고

 

dp가 dictionary니까 dp[i]에 dfs(i//p) + dfs(i//q)를 할당하면 저장도 된다

 

from sys import stdin

def dfs(i,dp):
    
    #만약 A[i]를 이미 구했다면, 그대로 접근해서 return
    if dp.get(i,0) != 0:
        
        return dp[i]
    
    #A[i]를 구하지 않았다면,
    else:
        
        #i//p와 i//q를 재귀호출해서 A[i]를 구한다
        dp[i] = dfs(i//p,dp)+dfs(i//q,dp)

        return dp[i]

n,p,q = map(int,stdin.readline().split())

#A[n]을 저장할 dict
dp = {}

#A[0] = 1
dp[0] = 1

print(dfs(n,dp))

 

 

dictionary와 재귀를 이용해서 원하는 값만 저장해서 목적지에 도달할 수 있다