[백준] C++ 16194번(카드 구매하기2)

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

 

문제 해결 방법

1. 카드의 개수에 따른 최솟값을 DP에 저장한다.

 

1개의 카드를 갖기 위해 지불해야 하는 최솟값을 구한다.

2개의 카드를 갖기 위해 지불해야 하는 최솟값을 구한다.

.

.

.

N개의 카드를 갖기 위해 지불해야하는 최솟값을 구한다.

 

카드의 개수가 늘어날수록 사용할 수 있는 카드의 종류가 늘어난다.

종류가 늘어남에 따라 값이 감소하는지 관찰하고 감소한다면 갱신해준다.

#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];
		DP[i]=987654321;
	}
	
	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;
}