[C++][백준 BOJ] 2294 동전2 / DP

C++ / 백준 2294 동전2

---

문제 

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

2294번: 동전 2

 

---

해설

 

1️⃣dp의 초기값을 "최대값"으로 설정 

	#define INF 123456789
    
    	for (int i = 0; i <= N; i++)
	{
		dp[i] = INF;
	}

 

2️⃣coin이 1일때

⚡coin이 1일때 , 만들 수 있는 값의 범위가 1~N

 

3️⃣coin이 5일때

⚡coin이 5일때 , 만들 수 있는 값의 범위가 5~N

 

4️⃣coin이 12일때

⚡coin이 12일때 , 만들 수 있는 값의 범위가 12~N

 

---

코드

using namespace std;
#include <iostream>
#include <vector>
#include <algorithm> // sort

#define MAX 10001
#define INF 123456789

int N;
int M;
int coin[MAX];
int dp[MAX];

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

	// 백준 2294 동전2
	cin >> N >> M;

	// dp 배열에 작은 동전부터 개수 갱신, 
	// 다음동전이랑 최솟값 저장
	for (int i = 0; i < N; i++)
	{
		cin >> coin[i]; // 동전 담아놓는 배열
	}

	// 최소값을 구해야 하기 때문에
	for (int i = 0; i <= M; i++) {
		dp[i] = INF;
		//dp배열에 최댓값으로 설정
	}

	dp[0] = 0;
	// dp[n] = 합이 n인 동전 갯수
	for (int i = 0; i < N; i++) // 1 5 12
	{
		for (int j = coin[i]; j <= M; j++)
		{
			dp[j] = min(dp[j], dp[j - coin[i]] + 1);
			// 1일때는 처음부터~15
			// 5일때는 5~15
			// 12일때는 12~15
		}
	}

	if (dp[M] == INF)
	{
		cout << -1;
	}
	else
	{
		cout << dp[M];
	}

 

https://github.com/churush912837465

churush912837465 - Overview