오늘의 문제- boj-1351

문제

무한 수열 A는 다음과 같다.

A[0] = 1
A[i] = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)
N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

풀이

점화식이 이미 주어져 있는 골드5치고는 쉬운 문제다.
그래서 만만하게 보고 for문을 돌면서 dp값을 채우는 로직을 짰는데 메모리 초과가 났다. 그래서 재귀함수로 바꿔서 최대한 연산수를 줄였는데 의미가 없었다.

그래서 생각해보니 애초에 dp테이블을 N+1개로 설정한 것 자체가 문제가 될 수 있겠다고 생각해서 문제를 풀어보려다 못참고 아래의 알고리즘 분류태그를 봐버렸다.

해시를 사용한 집합과 맵이라고 적힌 분류를 보고 dp테이블을 엄청 크게 초기화하는 것보다 이렇게 컴팩트하게 만들 수도 있겠다 싶어서 defaultdict를 활용해서 풀었다.

from collections import defaultdict
N, P, Q = map(int, input().split())

dp = defaultdict(int)

dp[0] = 1

def get_value(N, P, Q):
    if dp[N] != 0:
        return dp[N]
    dp[N] = get_value(N//P, P, Q) + get_value(N//Q, P, Q)
    return dp[N]
    

print(get_value(N, P, Q))

피드백

내가 dp에서 어려워하는 부분은 점화식을 도출하는 것이기 때문에 이런 문제보다는 점화식을 한번에 도출해내기 어려운 문제를 푸는 것이 나에게 더 도움이 될 것 같다.