문제 URL:
11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
카드가 1개가 포함되어 있는 카드부터 N개가 포함되어 있는 카드까지 각각의 카드팩이 존재한다. 각 카드팩의 가격이 주어질 때, 원하는 개수의 카드팩을 사는 최대 비용을 출력하는 프로그램을 작성하자.
먼저 카드팩의 가격을 arr[i]에 담고
이전 카드팩의 최대 비용인 dp[i-j]에 arr에 담긴 카드팩의 가격을 하나씩 추가해서 최댓값을 구하면 된다.
ex. 카드 4개를 구매할 때 dp[3] + arr[1], dp[2] + arr[2]를 비교하여 더 큰 값을 dp[4]에 대입
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int arr[10001];
int dp[10001];
int main(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> arr[i];
}
dp[0] = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= i; j++){
dp[i] = max(dp[i], arr[j] + dp[i - j]);
}
}
cout << dp[n];
return 0;
}