[BOJ] 16194번_카드 구매하기 2_DP (C++)

[문제]

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

돈을 최소로 지불해서 카드 N개를 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 카드 4개를 사기위해 지불해야 하는 최소 금액은 4원이다. 1개짜리 4개를 사면 되기 때문이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 지불해야하는 최소 금액을 구하는 문제이다.

N개보다 많은 개수의 카드를 산 다음 나머지 카드를 버려서 N개를 만드는 것은 불가능하다.

[사용 알고리즘]

DP(다이나믹 프로그래밍)

[풀이 핵심]

• 카드팩을 구매할 때 지불해야하는 최소 금액일 수 있는 경우는 2가지가 있다. 첫번째는 i장을 살 때 i장이 들어있는 팩을 사는 경우이고 두번째는 이전까지 최소금액 + 카드팩 1개를 사는 경우이다. 이게 무슨 뜻이냐면 예를 들어 카드 4개를 구매하려고 할 때, 카드 1개를 구매하는 최소값 + 카드가 3개 들어있는 카드팩의 가격, 카드 2개를 구매하는 최소값 + 카드가 2개 들어있는 카드팩의 가격, 카드 3개를 구매하는 최소값 + 카드개 1개 들어있는 카드팩의 가격 중 가장 최소 금액을 구하는 것이다.

[코드]

//boj16194번_카드 구매하기 2_dp

#include <iostream>

using namespace std;

int dp[1001];
int card[1001];

int main() {
	int N;
	cin >> N;

	for (int i = 1; i <= N; i++) {
		cin >> card[i];
	}

	dp[1] = card[1];

	for (int i = 2; i <= N; i++) {
		dp[i] = card[i];
		for (int j = 1; j <= i; j++) {
			dp[i] = min(dp[i], dp[i - j] + card[j]);
		}
	}
	cout << dp[N];

	return 0;
}