728x90
반응형
문제:
무한 수열 A는 다음과 같다.
- A0 = 1
- Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)
N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 3개의 정수 N, P, Q가 주어진다.
출력:
첫째 줄에 AN을 출력한다.
풀이방법:
문제에서 명확하게 점화식이 주어졌기 때문에 다이나믹 프로그래밍을 사용하도록 한다. 하지만 주어진 조건의 N, P, Q이 매우 크기 때문에 list를 사용해서 구현을 한다면 메모리가 터지는 문제점이 있다. 따라서 최대한 쓰지 않는(비어있는) 값들을 줄이기 위해서 dict 자료형에다가 값들을 mapping 하도록 한다. 빠른 구현을 위해서 defaultdict을 사용해 초기화하는 과정을 간단하게 구현할 수 있도록 했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
from collections import defaultdict
def infinite(n):
global dp
if dp[n]:
return dp[n]
else:
dp[n] = infinite(n//P) + infinite(n//Q)
return dp[n]
N, P, Q = map(int,input().split())
#list를 사용하면 N이 개크면 메모리가 터짐
dp = defaultdict(int)
dp[0] = 1
infinite(N)
print(dp[N])
|
cs |
문제링크:
https://www.acmicpc.net/problem/1351
1351번: 무한 수열
첫째 줄에 3개의 정수 N, P, Q가 주어진다.
www.acmicpc.net
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]12904. A와 B (0) | 2021.09.28 |
|---|---|
| [BOJ]1722. 순열의 순서 (0) | 2021.09.27 |
| [BOJ]1202. 보석 도둑 (0) | 2021.09.23 |
| [BOJ]1057. 토너먼트 (0) | 2021.09.16 |
| [BOJ] 14890. 경사로 (0) | 2021.09.15 |