[백준/Python]1351: 무한 수열

문제

https://www.acmicpc.net/problem/1351
백준 문제집 - 0x15강 - 해시

 

알고리즘: 해시를 사용한 집합과 맵, 다이나믹 프로그래밍

---

풀이

 

피보나치와 비슷한 문제라고 생각하면 되겠다.
A[0] = 1이니 임의의 값 A[N]을 N = 0이 될 때까지 식에 맞춰 쪼개면 된다.

 

💡참고로 ⌊ ⌋ 기호는 바닥함수(floor function)를 나타낸다.
⌊x⌋ = x보다 작거나 같은 가장 큰 정수 를 의미한다.
즉, ⌊i/P⌋ = i // P인 셈이다.

 

따라서 딕셔너리에 A[0] = 1을 미리 저장해주고, N이 0이 될때까지 아래의 과정을 반복한다.

1. A[N]의 값이 딕셔너리에 존재한다면 그 값을 반환
2. 없다면 재귀를 통해 A[N] = A[N//P] + A[N//Q]의 값을 구하고 딕셔너리에 저장

 

전체 코드

# 재귀 + 메모이제이션 문제.
# 메모리: 32544KB / 시간: 40ms
from sys import stdin


input = stdin.readline

N, P, Q = map(int, input().split())

memo = {0: 1}  # A0 = 1

def dfs(num):
    # Anum이 memo에 존재한다면 해당 값 return
    if num in memo:
        return memo[num]

    ret = dfs(num // P) + dfs(num // Q)
    memo[num] = ret
    return ret

print(dfs(N))