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

문제

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

16194번: 카드 구매하기 2

풀이

처음에 DP 테이블을 P(i)를 활용해서 초기화 해주었다.

이후 점화식을 세워주었다.

최솟값(dp[i]) = 비용의 최솟값을 구해야하므로 기존에 i장을 구매하기위해 필요한 비용(dp[i])과  i - j장을 구매하기위해 필요한 비용 + j장을 구매하기위해 필요한 비용(dp[i - j] + arr[j]) 중 최솟값이라는 점화식을 도출해낼 수 있었고 이를통해 문제를 해결할 수 있었다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int dp[1001];
int arr[1001];

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;

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

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			dp[i] = min(dp[i], dp[i - j] + arr[j]);
		}
	}

	cout << dp[n];
}