[백준 BOJ][C++]11052번 카드 구매하기: DP

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

 

 

 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. 

 

 dp[n] 은 카드 n장을 만들기 위해 필요한 금액의 최댓값을 나타냅니다. 

 

 카드 i개가 포함된 팩의 가격 P[i]와 dp에 저장되어 있는 수들을 조합하여 해결할 수 있습니다. 

 

 그렇다면 dp[1]은 카드 1장을 만들기 위한 금액의 최댓값이므로 자동으로 P[1]이 되는 것이지요.

 

 다음으로 dp[2]의 값은 어떻게 될까요? P[2]와 dp[1]+dp[1]을 비교하여 더 큰 값으로 설정하면 됩니다. 

 

 예제 (1) 입력 예시인 N=4, P[]={1, 5, 6, 7}을 바탕으로 연산 과정을 보겠습니다. 

 

n	P[n]	dp[n] 후보들	dp[n]
1	1	P[1]	1
2	5	P[2] vs dp[1]+dp[1] ( 5  vs  1 + 1 )	5
3	6	P[3] vs dp[2]+dp[1] ( 6  vs  5 + 1 )	6
4	7	P[4] vs dp[3]+dp[1] vs dp[2]+dp[2] ( 7  vs  6 + 1  vs  5 + 5 )	10

 

 다음 코드에서 중첩 for문의 안 쪽 for문 조건식을 j >= i/2 로 한 이유는 j>=1로 하게 되면 똑같은 후보를 비교하게 되기 때문입니다. 

 

 예를들어 dp[4]를 구할 때 후보가 P[4] vs dp[3]+dp[1] vs dp[2]+dp[2] 인데 j>=1까지 하게 되면 dp[1]+dp[3]도 비교합니다. 이는 dp[3]+dp[1]과 똑같으므로 비교하는 의미가 없겠지요!

 

#include<iostream>
#include<algorithm>
#include<cstdlib>

using namespace std;

int dp[1001] = { 0, };
int p[10001];

int main(void) {

	int n;

	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> p[i];
	
	dp[1] = p[1];

	for (int i = 2; i <= n; i++) {
		int maxnum = p[i];
		for (int j = i - 1; j >= i / 2; j--) {
			maxnum = max(maxnum, dp[i - j] + dp[j]);
		}
		dp[i] = maxnum;
	}

	cout << dp[n];

	return 0;
}