99클럽 코테 스터디 _ 25일차 TIL (동적 계획법, 메모이제이션)

 

< 문제 >

[백준] 1351. 무한 수열 / 골드5

---

< 풀이 >

Dynamic Programming
시간복잡도 : O(logN)

 

def f():
    N, P, Q = map(int, input().split())
    dp = {0:1}  # 딕셔너리 기반 메모이제이션  # dp[0] = 1

    def memo(n):
        if n in dp:  # 이미 계산된 값이면 그대로 반환
            return dp[n]
        dp[n] = memo(n // P) + memo(n // Q)
        return dp[n]

    print(memo(N))

f()

 

 

 

풀이 방식

1. dp 초기화
   • dp = {0: 1} : dp [0]은 문제의 기본 조건으로 1로 초기화한다.
2. 재귀 함수 memo(n) 정의
   • 메모이제이션 활용
     • dp[n]이 이미 계산된 값이면 딕셔너리에서 그대로 반환
   • 점화식 적용
     • dp[n] = dp[n//P] + dp[n//Q]
     • memo(n//P) + memo(n//Q)를 dp[n] 값으로 저장

---

< 회고 >

🤔 💭_

재귀 함수와 메모이제이션으로 점화식을 빠르게 계산하는 방식에 대한 고민을 해볼 수 있었다.

dp[n//P] + dp[n//Q]를 그대로 구현하면 N값이 10000000이 들어오는 경우 시간이 굉장히 오래 걸리게 된다.

그래서 dp도 기존에는 리스트를 썼지만, 본 문제에서는 딕셔너리를 사용해서 시간 복잡도를 줄였다.