백준 1351 - 무한 수열 (Python)

문제 https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 풀이 n, p, q = map(int,input().split()) memo = {} memo[0] = 1 def a(i): if i not in memo: memo[i] = a(i//p) + a(i//q) return memo[i] print(a(n)) n의 크기가 0 ≤ N ≤ 10^12 로 매우 크므로 DP 중 tabulation 방식으로는 풀수가 없었다. 크기가 10^12인 배열을 생성하니 그냥 오류를 뱉어 버리더라... 그래서 딕셔너리와 재귀함수를 이용하여 memoization 방식으로 구현해주었다. 재귀함수를 통해 a(i)..

2024.02.12