 |
|
" 문제 "
제목 :www.acmicpc.net/problem/11052
11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
" 아이디어 "
D[i] = 카드 i개를 구매하는 최대 비용
P[j] = j번째 카드팩의 비용
i-j개의 카드 + j번째 카드팩(마지막에 구매) = i개의 카드 (최종)
-> D[i] = max ( D[i-j] + P[j] ) ( j>=1, j<=i)
D[0] = 0 (초기값)
" 코드 "
|
1
2
3
4
5
6
7
8
9
|
n = int(input())
p = [0] + list(map(int, input().split()))
d = [0]*(n+1)
for i in range(1,n+1):
for j in range(1,i+1):
d[i] = max(d[i], d[i-j]+p[j])
print(d[n])
|
cs |
" 참고자료 "
반응형
'알고리즘 > Baekjoon' 카테고리의 다른 글
| [ Baekjoon : python ] 백준 1439번 뒤집기 - 그리디 알고리즘 (0) | 2021.03.27 |
|---|---|
| [ Baekjoon : python ] 백준 15990번 1, 2, 3 더하기 5 - 다이나믹프로그래밍 (0) | 2021.02.23 |
| [ Baekjoon : python ] 백준 9095번 1, 2, 3 더하기 - 다이나믹프로그래밍 (0) | 2021.02.20 |
| [ Baekjoon : python ] 백준 11727 2×n 타일링 2 - 다이나믹프로그래밍 (0) | 2021.02.20 |
| [ Baekjoon : python ] 백준 11726 2xn 타일링 - 다이나믹프로그래밍 (0) | 2021.02.20 |
