[Inflearn] 동전교환(DP, 냅색 알고리즘, knapsack algorithm)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

- 거스름돈을 가장 적은 수의 동전으로 교환

- 각 단위의 동전은 무한정 사용 가능

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

3 (동전 종류 개수)

1 2 5 (동전 종류)

15 (거슬러 줄 금액)

전 문제와 유사하게 dp[]를 금액의 한계로 정하고,

1원부터 15원까지 모든 동전을 사용해보면 된다.

d[j]는 j원을 거슬러주는데 사용된 동전의 최소 개수이다.

j = 8이라면 8월을 거술러주는데 사용된 동전의 최소 개수.

dp[]의 변화를 살펴보면

초기 상태

1원을 사용할 경우,

2원을 사용할 경우,

5원을 사용할 경우

결과로는 15원을 거슬러 줄 때, 5원짜리 3개로 거슬러 주는 것이 가장 동전을 적게 사용할 수 있음.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <cstdio> #include <vector> #include <algorithm> using namespace std; #define MAX 2147000000 #define MIN -2147000000   int main(void) {     int N, M, i, j;     freopen("input.txt", "rt", stdin);     scanf("%d", &N);     vector<int> coin(N);     for (i = 0; i < N; i++)         scanf("%d", &coin[i]);          scanf("%d", &M);     vector<int> dp(M + 1, MAX);     dp[0] = 0;       for (i = 0; i < N; i++) {         for (j = coin[i]; j <= M; j++) {             dp[j] = min(dp[j], dp[j - coin[i]] + 1);         }     }       printf("%d\n", dp[M]);       return 0; } Colored by Color Scripter

cs

line 18) 최소 개수를 구해야 하므로, dp를 큰 값으로 초기화

line 19) 직관적은 문제의 해 dp[0]은 0으로 초기화

line 21~25) 모든 동전을 모든 거슬러 줄 동전의 한계에 적용

line 23) 기존에 거슬러 줄 동전의 최소 개수와 

          다른 동전으로 거슬러주었을 때의 동전의 최소 개수의 min

#. Teach code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include<bits/stdc++.h> using namespace std;   int main(){     ios_base::sync_with_stdio(false);     int n, m;     cin>>n;     vector<int> coin(n);     for(int i=0; i<n; i++) cin>>coin[i];     cin>>m;     vector<int> dy(m+1, 1000);     dy[0]=0;     for(int i=0; i<n; i++){         for(int j=coin[i]; j<=m; j++){             dy[j]=min(dy[j], dy[j-coin[i]]+1);         }     }     cout<<dy[m];     return 0; } Colored by Color Scripter

cs

line 11) 1,000으로 초기화해준 이유는,

     거슬러 줄 최대 금액이 500원이고, 동전의 최소 단위는 1이므로

     최악의 상황일 경우 500개의 동전이 필요하게 된다.

     그래도 넉넉하게 1,000으로 초기화

     

#. Result

  - Input --------------------------------------------------------

3

1 2 5

15

------------------------------------------------------------------

  - Output --------------------------------------------------------

3

------------------------------------------------------------------