[BOJ/python] 1351: 무한 수열

문제

gold 5 / 다이나믹 프로그래밍, 자료 구조, 해시를 사용한 집합과 맵

문제 흐름

사실 해시에 대한 문제들을 풀고있기 때문에 당연히 해시라고 생각하고 문제를 읽었는데
이거.. dp 아닌가? 하는 생각이 들었다.
하지만 n, n+1, n+2 와 같이 순차적으로 저장되는 게 아니기 때문에 일반 배열을 이용한다면 불필요하게 공간이 많이 낭비되겠다고 생각됐다.
이런 부분에서 hash를 이용해주면 적절하게 이용되겠다.

1. 0번째 수 1을 의미하는 key-value 값을 넣은 딕셔너리(수열 저장), 찾아야 하는 수인 n이 들어간 스택 생성
2. 스택에서 pop했을 때(i) i번째 수를 현재 딕셔너리에서 만들 수 없다면 i와 필요한 수의 번째 수(i//p 또는 i//q)를 순서대로 다시 스택에 넣어준다.
3. i번째 수를 현재 딕셔너리에서 만들 수 있다면 만들어 딕셔너리에 저장해준다.
4. 위 과정을 반복한다.

사실 작성하면서 너무 비효율적이게 되면 어떡하나 생각했는데 다행히도 정답으로 체크되긴 했다.

코드

# 무한 수열
# hash DP

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n, p, q = map(int, input().split())

    d = {0: 1}
    st = [n]
    while not d.get(n, 0):
        i = st.pop()
        if not d.get(i//p, 0):
            st.append(i)
            st.append(i//p)
        elif not d.get(i//q, 0):
            st.append(i)
            st.append(i//q)
        else:
            d[i] = d[i//p] + d[i//q]
        
    print(d[n])

마무리

dp는 항상 어려워해서 살짝 고민도 하고 정의도 찾아봤다.
하지만 직관적이기 때문에 어려운 문제는 아닌 것 같다.