[210512][백준/BOJ] 16194번 카드 구매하기 2

문제

입출력

풀이

백준 11052 카드 구매하기는 최대값을 구하는 문제였는데
백준 16194 카드 구매하기2는 최소값을 구하는 문제이다.

카드 구매하기를 푼 상태에서 단순하게 max를 min으로 바꾸면 해결이 될까 생각했는데 결과값이 0이 나왔다.
이는 d 배열을 전역변수로 선언해서 초기값이 0이 들어가 있는 상태이기 때문이다.
이 상태에서 min으로 최소값을 찾으려하면 0이 최소값이므로 0이 출력되는 것이다.

따라서 d[1] = A[1]만 초기화를 해주는 것이 아니라 d[1]부터 d[n]까지 각각 A[1]~A[n]으로 초기화를 해주면 문제를 해결할 수 있다.

코드

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

int d[100002];
int A[100002];

int dp(int n)
{
	for (int i = 1; i <= n; ++i)
		d[i] = A[i];

	for (int i = 2; i <= n; ++i)
		for (int j = 1; j <= i; ++j)
			d[i] = min(d[i], d[i - j] + A[j]);
	return d[n];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> A[i];

	cout << dp(n);
}