[Hash] 백준 1351번 “무한 수열” Python 풀이

문제 링크

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

풀이

• 해당 문제는 DP 또는 Hash로 해결할 수 있습니다.
• 해당 포스트에선 Hash를 사용한 해결 방법을 다루고 있으며,
• n번째 값을 딕셔너리에 저장하는 재귀 함수를 통해 해결할 수 있습니다.

코드

import sys

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

# 딕셔너리 선언
dict = {}
dict[0] = 1

def solution(n):

    # n번째 값이 저장되어있다면, 그대로 반환
    if (n in dict):
        return dict[n]
    # n번째 값이 저장되어있지 않다면, n번째 값을 계산 및 저장한 뒤, 반환
    else:
        dict[n] = solution(n//p) + solution(n//q)
        return dict[n]

print(solution(n))