[백준 11052번 C++] 카드 구매하기
11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
[이해하기]
카드의 등급으로 나타나지는 색은.... 왜 주어진거지?
필요없는 설명 아닌가?
여튼
예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.
P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.
마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.
카드 4개를 갖기 위해서는
1 * 4 / 1 + 3 / 2 * 2 / 4 * 1 의 경우가 있다
그럼 각각의 경우 지불하는 돈은
1*4 = 4 / 1+6 = 7 / 5*2 = 10 / 7 이므로 최댓값은 10이다
arr[a] = 입력값(카드 a의 가격)
dp[a] = a개의 카드를 구매했을 때의 최대 비용
마지막에 선택하는 카드가 P1이라면? 최대 비용은 dp[n-1] + arr[1]
마지막에 선택하는 카드가 P2라면? 최대비용은 dp[n-2] + arr[2]
마지막에 선택하는 카드가 P3이라면? 최대비용은 dp[n-3] + arr[3]
마지막에 선택하는 카드가 P4라면? 최대비용은 arr[4]
최종적으로 n개를 선택하는 최대 비용은 이 중 가장 큰 것!
dp[0] = 0
dp[1] = arr[1] (1개를 구매하는 방법은 P1 하나 선택하는 방법밖에 없음)
dp[2] = max(arr[1] *2, arr[2])
-> dp[n] = max(dp[n], dp[n-i] + arr[i])
[참고]
[ 백준 11052 ] 카드 구매하기 (C++) :: 얍문's Coding World.. (tistory.com)
[ 백준 11052 ] 카드 구매하기 (C++)
백준의 카드구매하기(11052) 문제이다. ( 문제 바로가기 ) [ 문제를 다시 푸는 과정에서 보다 구체적이고 상세한 설명으로 이 문제를 다시 포스팅 하였습니다. 아래의 글을 참고하셔서 풀이하셔도
yabmoons.tistory.com
코드로 표현해보면..!
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
//카드값 입력 받기
int arr[n+1] = {0, };
for(int i=1; i<=n; i++){
cin >> arr[i];
}
//카드를 a개 샀을 때의 최대 비용을 저장하기 위한 배열 선언
int dp[n+1] = {0, };
//for문을 돌면서 카드를 a개 샀을 때의 최대 비용을 모두 저장함
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
dp[i] = max(dp[i], dp[i - j] + arr[j]);
}
}
//최종적으로 dp[n]이 카드 n개를 샀을 때의 최대 비용
cout << dp[n] << endl;
return 0;
}n=4, arr={0,1,5,6,7}, dp={0} 의 경우
이중 for문을 돌 때 dp의 저장 과정을 구해보면
dp[1] = max(dp[1], dp[0]+arr[1])
=> dp[1] = 1
---------------------------------------------------------------
dp[2] = max(dp[2], dp[1]+arr[1])
= 2
dp[2] = max(dp[2], dp[0]+arr[2])
= max(2, 5)
= 5
=> dp[2] = 5
---------------------------------------------------------------
dp[3] = max(dp[3], dp[2]+arr[1])
= 6
dp[3] = max(dp[3], dp[1]+arr[2])
= max(6, 1+5)
= 6
dp[3] = max(dp[3], dp[0]+arr[3])
= max(6, 6)
= 6
=> dp[3] = 6
---------------------------------------------------------------
dp[4] = max(dp[4], dp[3]+arr[1])
= 7
dp[4] = max(dp[4], dp[2]+arr[2])
= max(7, 5+5)
= 10
dp[4] = max(dp[4], dp[1]+arr[3])
= max(10, 1+6)
= 10
dp[4] = max(dp[4], dp[0]+arr[4])
= max(10, 7)
= 10
---------------------------------------------------------------
=======> dp[4] = 10