[백준] C++ 11052(카드 구매하기)

 

#include <iostream>

using namespace std;

int arr[1001];
int DP[1001];

int main(void)
{
	int a=0;
	
	cin>>a;
	
	for(int i=1; i<=a; i++)
	{
		cin>>arr[i];
	}
	
	for(int i=1; i<=a; i++)
	{
		for(int j=1; j<=a; j++)
		{
			if(i-j>=0)
			{
				if(DP[i]<arr[j]+DP[i-j])
				{
					DP[i]=arr[j]+DP[i-j];
				}
				
			}
			else
			{
				break;
			}
		}
	}
	
	cout<<DP[a];
	
	return 0;
}

 

P1 = 5, P2 = 2, P3 = 8, P4 = 10

 

P1 카드팩에 1장이 들어있고 5원

P2 카드팩에 2장이 들어있고 2원

P3 카드팩에 3장이 들어있고 8원

P4 카드팩에 4장이 들어있고 10원

 

카드 N개를 갖기 위해 지불해야 하는 최댓값을 구하는 문제이다.

 

흠 어떻게 접근해야 좋을까??

 

나는 카드 1~N장에 필요한 최댓값을 구하는 방법으로 해결하였다.

 

카드 1장에 대한 경우의 수

P1 카드팩을 1개를 사는 경우(5원)

 

카드 2장에 대한 경우의 수

P1 카드팩을 2개를 사는 경우(10원)

P2 카드팩을 1개 사는 경우(2원)

 

카드 3장에 대한 경우의 수

P1 카드팩을 3개 사는 경우(15원)

P1 카드팩을 1개 사고 P2 카드팩을 1개 사는 경우(7원)

P3 카드팩을 1개 사는 경우(8원)

 

카드 4장에 대한 경우의 수

P1 카드팩을 4장 사는 경우(20원)

P1 카드팩을 1장 사고 P3 카드팩을 1 장사는 경우(13원)

P2 카드팩을 2장 사는 경우(4원)

P4 카드팩을 1개를 사는 경우(10원)

 

그림이 조금 조잡하긴 한데 이런 흐름으로 진행된다.

카드 1장의 최댓값을 구하고

이걸 이용해서 카드 2장의 최댓값을 구하고

또 이걸 이용해서 카드 3장의 최댓값을 구한다.

 

각 개수의 최댓값을 구한 뒤 그 값과 어떠한 카드팩을 추가했을 때 값이 N이 되는 값 중에서 가장 큰 값을 저장한다. 

 

if(DP[i]<arr[j]+DP[i-j])
{
       DP[i]=arr[j]+DP[i-j];
}