11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
[알고리즘]
DP
[접근 방법]
N개의 카드 팩이 있고, N개의 카드를 구매하는 상황.
D[i] = 카드 i개를 구매하는 최대 비용, dp[k] = 카드 k개가 들어있는 카드팩의 가격 일 때,
카드 i개를 구매하는 최대 비용의 경우의 수는
D[1] + dp[i - 1]
D[2] + dp[i - 1]
D[3] + dp[i - 3]
...
D[i] + dp[0]
[코드]
|
1
2
3
4
5
6
7
8
9
10
11
|
N = int(input())
N_list = list(map(int, input().split()))
N_list = [0] + N_list
dp = [0] * 1001
for i in range (N + 1) :
for j in range(i + 1) :
# 최대값을 찾기 -> j증가시키기 전 가격( dp[i] ) & j+1된 가격 max로 비교하여 갱신
# (j+1된 가격 -> N_list[j] + dp[i - j])
dp[i] = max(dp[i], N_list[j] + dp[i - j])
print(max(dp))
|
cs |
'Algorithm > Dynamic Programming' 카테고리의 다른 글
| [Algorithm/Java] 다이나믹 프로그래밍 복습 (0) | 2022.07.14 |
|---|---|
| [Python] 백준 #1932 정수 삼각형 (0) | 2021.06.30 |
| [Python] 백준 #1149 RGB거리 (0) | 2021.06.30 |