[C++] 백준(BOJ) - 2294 : 동전 2

12 Apr 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 2294 : 동전 2(링크)

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

알고리즘

1. DP
2. 냅색

풀이

• 냅색 문제
  • n가지를 무한히 사용할 수 있을 때는 DP를 왼쪽부터 누적 시키기
  • n가지를 1개만 사용할 수 있을 때는 DP를 오른쪽부터 누적 시키기

코드

// BOJ - 2294 : 동전 2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF = 2147000000;
int n, k, a[10004], tmp;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> k;

	fill(a, a + 10004, INF);
	a[0] = 0;

	for (int i = 0; i < n; i++)
	{
		cin >> tmp;
		for (int j = tmp; j <= k; j++)
		{
			a[j] = min(a[j], a[j - tmp] + 1);
		}
	}
	if (a[k] == INF) cout << -1 << '\n';
	else cout << a[k] << "\n";
	return 0;
}

평가

• 냅색 문제
  • 점화식 : dp[j] = max(dp[j], d[j-w] + v)
  • 가방에 j무게만큼 들어갈 때 보석의 최대 가치 구하는 문제 (각 종류별 보석의 개수는 무한대)