[BOJ] 2294번 : 동전 2

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
const int val = 10005;
int coins[val]; 
int d[val];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k; 
	cin >> n >> k; 
	for (int i = 1; i <= n; i++) cin >> coins[i]; 
	
	d[0] = 0; 
	for (int i = 1; i <= k; i++) {
		d[i] = 10001;
		for (int c = 1; c <= n; c++) {
			if (coins[c] > i) continue;
			if (d[i-coins[c]] == 10001) continue;
			d[i] = min(d[i], d[i - coins[c]] + 1);
		}
	}
	if (d[k] == 10001) cout << -1 << "\n";
	else cout << d[k] << "\n";
}

dp를 이용해 풀었다. 따라서, 세 가지 스텝을 따른다. 

1. 테이블을 정의한다. d [i] = i원을 만들 수 있는 동전의 최솟값 

2. 점화식을 작성한다. d [i] = min(d [i] , d [i-coins [c]] + 1) 

3. 초기값을 설정한다. d [0] = 0 

나는 d [i]를 101로 설정을 하는 바람에 계속 틀렸었다. 왜 101로 설정했었냐면, 동전의 개수가 100개가 최대니 깐, 중복을 생각하지 않았다. 따라서, d [i] = 10001로 초기값을 설정해야 한다. 

 

3. solution 2 :

// Authored by : jihwan0123
// Co-authored by : -
// http://boj.kr/a4f1202ad58a4973badecdf41c75c186
#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[10005], d[10005];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; i++)
    cin >> a[i];
  fill(d, d + 10005, 100005);
  d[0] = 0; // 0원: 0개
  for (int i = 0; i < n; i++) {
    for (int j = a[i]; j <= k; j++)
      // 동전 하나 추가한 값과 기존 값 중 작은값
      d[j] = min(d[j], d[j - a[i]] + 1);
  }

  cout << (d[k] == 100005 ? -1 : d[k]) << '\n';
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/2294.cpp

basic-algo-lecture/0x10/solutions/2294.cpp at master · encrypted-def/basic-algo-lecture

이렇게 코드를 짜는 게 더 효율적이다. 첫 번째 for문은 coins배열에 접근하기 위한 범위이고, 두 번째 for문은 금액을 만드는 for문이다. 따라서, 두 번째 for문에서는 현재 순서의 코인부터 시작하는 게 바람직하다.