[DP] BOJ 11052 카드 구매하기

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

11052번: 카드 구매하기

- 문제 파악

정수 N 과 P1~PN 의 정수가 주어진다. 1~N 을 적절히 조합하여 N을 만드는 수의 조합에서 Pi들의 합이 최대값을 출력하라.

 

-정답

 

1.  경우의 수

모든 경우의 수를 살펴 보지 않고 D[i-1] + D[1]만 확인했었다.

점화식을 찾는 도중 D[i-1] + D[1] = D[i-2] + D[2] 를 찾았고, 시간 초과를 염려해서 2중for문을 기피하려고 했다.

하지만 위 점화식은 여러 조합이 있을때는 매우 취약했다.

 

2. D[i] = tmp;  - > D[i] = max(tmp, D[i]); 

모든 경우의 수를 도는 만큼 이미 최대값이 D[i] 에 있음에도 그보다 작은 값이 입력되는 경우가 있었다.

 

시간 초과를 두려워 하지말자.

디버깅을 좀 더 꼼꼼히 하자.

 

#include "bits/stdc++.h"
using namespace std;

int D[1002]; // 팩의 개수에 대한 최대값
int arr[1002]; // 입력 : 팩의 개수에 대한 값
int n;
int ans;


int main() 
{

	cin >> n;

	cin >> arr[1];
	D[1] = arr[1];

	for (int i = 2; i <= n; i++) 
	{	

		cin >> arr[i];

		for (int j = 0; j <= i / 2; j++)
		{
			int a = i - j;
			int b = i - a;

			int tmp = D[a] + D[b];
			if (tmp < arr[i])
			{
				D[i] = arr[i];

			}
			else
			{
				D[i] = max(tmp, D[i]);
			}

			ans = max(tmp, ans);
		}

		if(D[1] * i > D[i])
			ans = max(D[1]*i, ans);
	
	}

	ans = max(D[n], ans);

	cout << ans;
	return 0;

}