백준2294 - 동전2

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

2294번: 동전 2

2차원 dp를 이용하여 풀었다. 동전 i원일 때 j원을 만들 수 있는지 여부를 따졌다. i - 1원일 때 j원을 만들 수 있었는지 없었는지 판단하는 것이 중요하다.

 

i원으로 j원을 만들 수 있는 지 판별하는 방법은 다음과 같다.

 

1. 0번지를 1로 초기화하여 i원 동전 혼자 j원을 만들 수 있는 경우를 대비한다.

2. i원 보다 액수가 작은 j원은 i - 1원 일때의 j원을 만든 방법으로 초기화한다.

3. i원으로 j원을 만들 수 있는 경우는 i - 1원 일때 j원을 만들 수 있는 경우와 비교를 한다.

   3 - 1. i - 1로 j원을 만들 수 있는 경우는 i원으로 j원을 만들 수 있는 방법과 비교하여 더 작은 값을 채택한다.

   3 - 2. i - 1로 j원을 만들 수 없는 경우는 i - 1원으로 j원을 만들 수 있는 방법을 넣는다.

4. i원으로 j원을 만들 수 없는경우는 i - 1원 일때 j원을 만들 수 있는 경우를 넣는다.

 

ex.)

	0	1	2	3	4	5	6	7	8
2원 동전	1	0	1	0	2	0	3	0	4
3원 동전	1	0	1	1	2	2	2	3	3
5원 동전	1	0	1	1	2	1	2	2	2

 

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

int n, k;
int num;
int coin[101];
int mat[101][10001] = { 0, }; //i원 일때 j를 만들 수 있는 최소 경우의 수

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> coin[i];
	}
	
	sort(&coin[0], &coin[n + 1]); //우선 동전의 금액을 오름차순

	//첫번째 동전으로 만들 수 있는 j원을 찾아서 넣는다.
	for (int i = 0; i <= k; i++) {
		if (i == 0) {
			mat[1][0] = 1;
		}
		else {
			if (i % coin[1] == 0){
				mat[1][i] = i / coin[1];
			}
			else {
				mat[1][i] = 0;
			}
		}
	}

	for (int i = 2; i <= n; i++) { //i는 동전
		for (int j = 0; j <= k; j++) { //j는 액수
			if (j < coin[i]) { //현재 액수가 현재 동전의 액수보다 작은 경우
				mat[i][j] = mat[i - 1][j];
			}
			else if(mat[i - 1][j] == 0) { //coin[i]원 이전의 모든 동전들로도 j를 만들 수 없었을 경우
				if (mat[i][j - coin[i]] != 0) { //j원에서 coin[i]를 뺀 값이 존재하는 경우
					mat[i][j] = mat[i][j - coin[i]] + mat[i][coin[i]];
				}
			}
			else { //coin[i]원 이전의 모든 동전들로도 j를 만들 수 있을 경우
				if (mat[i][j - coin[i]] != 0) { //j원에서 coin[i]를 뺀 값이 존재하는 경우
					mat[i][j] = min(mat[i - 1][j], mat[i][j - coin[i]] + mat[i][coin[i]]);
				}
				else {
					mat[i][j] = mat[i - 1][j];
				}
			}
		}
	}

	if (mat[n][k] == 0) { //못 만들면
		cout << -1; //-1 출력
	}
	else {
		cout << mat[n][k];
	}
}