[백준] 2294번 : 동전2

🔗 문제 링크

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

---

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 목표 합인 k에 도달하기 위해 1원 ~ k원에 도달하기 위한 최소 개수의 동전을 dp에 저장하면서 이전 수에 대한 dp를 이용해 현재 수에 대한 값을 갱신하는 Bottom-Up 방식으로 풀었다.

1) 목표 합인 k를 입력 받아 저장하고, dp 배열의 모든 값을 가능한 동전 개수보다 더 큰 값(== INF)으로 초기화한다. (dp[i]가 INF라면 가지고 있는 동전들로 i까지 도달할 수 없는 경우이다.)

2) 동전의 가치들을 입력받아 units 배열에 저장하고, 이 가치들에 대한 dp를 1로 갱신한다.

• 만약 동전 가치가 2, 3이라고 하면 2와 3원에 도달하기 위한 최소 동전 개수는 1이 되는 것이다.

3) dp 배열을 1부터 k까지 갱신한다.

• dp[i]에는 i에 도달하기 위해 필요한 최소 동전 개수가 저장된다.
• 모든 각각의 동전 가치에 대해 아래 과정을 반복한다.
  • 만약 i - 현재 동전 가치 > 0을 만족한다면
  • 현재 동전 가치가 p일 때, dp[i]는 현재의 dp[i]와 i-p까지 도달하기 위해 필요한 최소 동전 개수 + 1 중 더 작은 수 이다.
  • 점화식 : dp[i] = min(dp[i], dp[i - p] + 1)
    • p : 현재 동전 가치(p는 units에 저장되어있는 모든 수)

4) dp[k]가 INF라면 -1을 출력하고, 아니라면 dp[k]를 그대로 출력한다.

✔️ 동작 과정

• 목표 값은 15이고, 동전 가치는 1, 5, 12

1) dp의 모든 값을 INF으로 초기화한다.

2) 동전 가치와 같은 인덱스의 dp를 1로 갱신한다.

3) i == 1일 때 dp[1] 갱신

• i - units에 대해 모든 units에서 0보다 작기 때문에 생략

4) i == 2일 때 dp[2] 갱신

• 2 - 1 > 0이므로 dp[2] = min(dp[2], dp[2 - 1] + 1) = 2

5) i == 3일 때 dp[3] 갱신

• 3 - 1 > 0이므로 dp[3] = min(dp[3], dp[3 - 1] + 1) = 3

6) i == 4일 때 dp[4] 갱신

• 4 - 1 > 0이므로 dp[4] = min(dp[4], dp[4 - 1] + 1) = 4

7) i == 5일 때 dp[5] 갱신

• 5 - 1 > 0이므로 dp[5] = min(dp[5], dp[5 - 1] + 1) = 1

7) i == 6일 때 dp[6] 갱신

• 6 - 1 > 0이므로 dp[6] = min(dp[6], dp[6 - 1] + 1) = 2
• 6 - 5 > 0이므로 dp[6] = min(dp[6], dp[6 - 5] + 1) = 2

8) 위와 같은 과정을 계속 반복한 결과 아래와 같이 dp 갱신됨.

---

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;
const int INF = 100001;
int dp[100001];
int units[101];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);	

	int n, k;
	cin >> n >> k;

	for (int i = 0; i <= k; i++)
		dp[i] = INF;

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

	for (int i = 1; i <= k; i++)
	{
		if (dp[i] == INF)
		{
			for (int j = 0; j < n; j++)
			{
				if (i - units[j] > 0)
					dp[i] = min(dp[i], dp[i - units[j]] + 1);
			}
		}
	}

	cout << ((dp[k] == INF) ? -1 : dp[k]);
}