https://www.acmicpc.net/problem/2294
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];
}
}
'백준' 카테고리의 다른 글
백준1697 - 숨바꼭질 (0) | 2020.02.03 |
---|---|
백준9251 - LCS (0) | 2020.02.02 |
백준5549 - 행성 탐사 (0) | 2020.01.31 |
백준1912 - 연속합 (0) | 2020.01.31 |
백준10844 - 쉬운 계단 수 (0) | 2020.01.30 |