[BOJ 2294] 동전 2

🔗Link

문제
풀이

💡Idea

1. 당연히 큰 동전을 많이 사용하는 것이 더 적은 개수로 만들 수 있다. 따라서 큰 동전부터 시도해보자.
2. 하지만 꼭 가장 큰 동전을 사용하는 것이 최적해는 아닐 수 있다. 따라서 작은 동전들의 경우도 모두 탐색해보자.
   • 1, 5, 12 -> 15
     1. 15 = 12 + 1 + 1 + 1
     2. 15 = 5 + 5 + 5

알고리즘 작동 방식

• n = 3, k = 15
• coin = {1, 5, 12}
• 방식:
  • 동전 합을 인덱스로 하고, 동전 개수를 값으로 하는 1차원 배열을 동전 종류 만큼 순회할 것이다.
  • 순회를 하며, 현재 값(동전 개수)이 -1이 아닐 때, 현재 동전 합에 현재 동전 종류의 값을 더한 값을 인덱스로 하는 값을 현재 값(동전 개수) + 1로 갱신한다.
• 시간복잡도: O(n·k)

순회/동전 종류	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0번 순회 / -	0	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1
1번 순회 / 12	0	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	1	-1	-1	-1
2번 순회 / 5	0	-1	-1	-1	-1	1	-1	-1	-1	-1	2	-1	1	-1	-1	3
3번 순회 / 1	0	1	2	3	4	1	2	3	4	5	2	3	1	2	3	3

🔑Code

/*
[동전 2] 
- date: 25.09.30
*/
#include <bits/stdc++.h>
using namespace std;

int n, k, coin[100];
int minCnt[10'001];

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> coin[i];
    
    sort(coin, coin+n, greater<int>());

    fill(minCnt + 1, minCnt + k + 1, -1); // minCnt[0] = 0

    for(int i = 0; i < n; i++){
        for(int j = 0; j <= k; j++){
            if(minCnt[j] == -1) continue; // 만들 수 있는 가지수가 아니면 패스

            int nv = j + coin[i];
            if(nv > k) continue; // 조건 k를 넘으면 패스

            int nv_cnt = minCnt[j] + 1;
            if(minCnt[nv] == -1 || nv_cnt < minCnt[nv]) minCnt[nv] = nv_cnt; // 더 적은 동전으로 만들 수 있다면 갱신
        }
    }
    
    cout << minCnt[k];

    return 0;
}

🗨️ Side Notes

알고리즘을 글로 표현하는 것은 참 어려운 것 같다.