[BOJ] 동전 2(2294)

[λ°±μ€€(BOJ)] 동전 2(2294) C++

문제 : BOJ_2294번 동전 2

문제 μ„€λͺ…

DP

DP둜 ν’€ 수 μžˆλŠ” 기본문제 동전 2μž…λ‹ˆλ‹€.
n 개의 동전이 주어지고, λ™μ „λ§ˆλ‹€ 값이 μ£Όμ–΄μ§‘λ‹ˆλ‹€.
μ΄λ•Œ 동전듀을 μ‘°ν•©ν•΄μ„œ 주어진 k의 값을 μ΅œμ†Œν•œμ˜ 동전을 μ¨μ„œ λ§žμΆ°μ•Ό ν•©λ‹ˆλ‹€.


Solution

큰 동전이 항상 μž‘μ€ λ™μ „μ˜ λ°°μˆ˜μž„μ΄ 보μž₯λœλ‹€λ©΄ 그리닀 ν•˜κ²Œ ν’€ 수 μžˆμ§€λ§Œ,
μœ„ λ¬Έμ œλŠ” 동전끼리 μ„œλ‘œ λ°°μˆ˜κ°€ μ•„λ‹Œ κ°’ 듀이기 λ•Œλ¬Έμ— dpλ₯Ό μ΄μš©ν•΄ 경우의 수λ₯Ό λ‹€ λ΄μ€˜μ•Ό ν•©λ‹ˆλ‹€.
1원 ~ k 원을 ν™•μΈν•˜λŠ” for λ¬Έμ•ˆμ— 1 ~ n 번째 동전을 μ΄μš©ν•˜λŠ” for 문으둜 2쀑 for 문이 ν•„μš”ν•©λ‹ˆλ‹€.
kλŠ” μ΅œλŒ€ 10,000이고 n은 μ΅œλŒ€ 100μ΄λ―€λ‘œ μ΅œλŒ€ for 문이 1,000,000μž…λ‹ˆλ‹€.
동전을 확인할 λ•Œ, 확인해야 ν•˜λŠ” λ™μ „μ˜ κ°’κ³Ό μ΅œμ†Œν•œμ˜ 수λ₯Ό 확인해야 ν•˜λŠ” 값이 κ°™λ‹€λ©΄ dp[κ°’] = 1둜 μ„ μ–Έν•©λ‹ˆλ‹€.
λ™μ „μ˜ 값이 μ΅œμ†Œν•œμ˜ 수λ₯Ό 확인해야 ν•˜λŠ” 값보닀 크닀면 μ΄μš©ν•  수 μ—†μœΌλ―€λ‘œ λ„˜μ–΄κ°‘λ‹ˆλ‹€.
λ™μ „μ˜ 값이 μ΅œμ†Œν•œμ˜ 수λ₯Ό 확인해야 ν•˜λŠ” 값보닀 μž‘λ‹€λ©΄

dp[κ°’] = min(dp[κ°’], (dp[κ°’ - λ™μ „μ˜ κ°’] + dp[λ™μ „μ˜ κ°’]));

으둜 ν•΄λ‹Ή κ°’μ˜ μ΅œμ†Ÿκ°’μ„ 계속 κ°±μ‹ ν•΄ μ€λ‹ˆλ‹€.


Description

  • μ΅œμ†Ÿκ°’μ„ κ°±μ‹ ν•˜κΈ° μ „ λͺ¨λ‘ INF κ°’μœΌλ‘œ dp 값을 μ΄ˆκΈ°ν™”ν•΄μ€λ‹ˆλ‹€.
  • λͺ¨λ“  for 문을 λ‹€ λŒμ•˜λŠ”λ°λ„ INF κ°’κ³Ό dp 값이 κ°™λ‹€λ©΄ λ™μ „μœΌλ‘œ λ§Œλ“€ 수 μ—†λŠ” κ°’μž…λ‹ˆλ‹€.
  • kκ°€ μ΅œλŒ€ 10,000μ΄λ―€λ‘œ, 10,001을 INF둜 μ •ν–ˆμŠ΅λ‹ˆλ‹€.

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 100001
using namespace std;
vector<int> coinValue;
vector<int> dp;
int main(void) {
	int n, k;
	cin >> n >> k;
	dp.resize(k + 1);
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		coinValue.push_back(num);
	}
	for (int i = 1; i <= k; i++) dp[i] = INF;
	for (int i = 1; i <= k; i++) {
		for (int j = 0; j < n; j++) {
			if (coinValue[j] == i) dp[i] = 1;
			else if (coinValue[j] < i) {
				dp[i] = min(dp[i], (dp[i - coinValue[j]] + dp[coinValue[j]]));
			}
		}
	}
	if (dp[k] == INF) cout << -1 << '\n';
	else cout << dp[k] << '\n';
	return 0;
}