[ 백준 2294 ] 동전2 (C++)

백준의 동전2(2294) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

간단한 예시를 하나 가지고 문제를 해결해보자.

우리에게 [ 1 , 2 , 3 ] 원짜리 동전이 있다고 가정하고, 이 때, 4원을 만들 수 있는 동전의 최소갯수를 구해보자.

지금부터 1원 ~ 6원까지 사용해야 하는 "동전의 최소갯수"에 초점을 맞춰서 계산해보자.

또한, "동전의 최소갯수"를 간단하게 수식으로 표현해보자. F[A] = B 라는 수식을 지금부터 사용할 것인데,

F[A] = B의 의미는 "A원을 만들 수 있는 동전의 최소갯수는 B개입니다." 를 의미한다.

또한 ! 지금부터 할 계산은 , "X원짜리 동전을 최종적으로 추가함으로써 K원 만들기" 를 해볼 것이다.

#Case1 : "1원짜리 동전을 최종적으로 사용"해서 1원 ~ 4원 만들기

1. 1원짜리 동전을 최종적으로 사용해서 1원 만들기.

- 가장 마지막에 1원짜리 동전을 추가함으로써 1원을 만드는 상황은, 현재 내가 "0원을 가지고 있는데, 이 상황에서 1원을

  최종적으로 추가하게 되면 1원이 될 수 있다. 즉 ! F[1] = 1이 된다.

2. 1원짜리 동전을 최종적으로 사용해서 2원 만들기.

- 가장 마지막에 1원짜리 동전을 추가함으로써 2원을 만드는 상황이다.

  그럼 기존의 상황은 어떤 상태여야할까 ?? 바로 "현재 내가 1원을 가지고 있는 상황" 이여야 한다.

  그래야지만, 위의 상황에서 '1원짜리 동전'을 추가함으로써 최종적으로 2원을 만들 수 있기 때문이다.

  그럼, 내가 1원을 가지고 있는 상황이여야 하는데, 이 때 필요한 동전의 최소갯수는 몇 개 일까 ??

  바로 위의 케이스에서 구한 F[1] = 1 이라는 식을 통해서, 이 값을 알 수 있다.

  즉, "1원을 만드는 최소 동전 갯수인 '1'개에서, 1원을 추가적으로 할당함으로써 2원을 만들었기 때문에, 결과적으로

  2원을 만드는데 필요한 최소 동전의 갯수는 '2개'가 된다." F[2] = 2

  그런데 ?! 사실 2원을 만드는데 필요한 동전의 최소갯수는 "2원짜리 1개만을 사용" 해서 1개로 만들 수가 있다.

  하지만 ! 아직 우리는 '2원짜리를 사용하는 경우'를 계산하지 않았기 때문에, 일단 임시적으로

  "현재까지 구한 결과값에 의하면, 2원을 만드는데 필요한 동전의 최소갯수는 2개" 라고 생각하자.

3. 1원짜리 동전을 최종적으로 사용해서 3원 만들기.

- 2원을 만드는 경우와 똑같이 계산을 하면 된다. 1원짜리 동전을 최종적으로 사용해서 3원을 만들기 위해서는

  기존의 상황은 "현재 내가 2원을 가지고 있는 상황" 이여야 하고, 이 상황에서 '1원'을 추가적으로 할당함으로써 3원을

  만들 수가 있다. 그럼 ! "현재 내가 2원을 가지고 있는 상황" 인데, 이 때 필요한 동전의 최소갯수는 몇 개 일까 ??

  이 결과값 또한 우리는 이미 알고 있다. 왜냐하면 위의 케이스에서 F[2]의 값에 저장되어 있기 때문이다.

  즉 ! F[3] = 3 이 된다. 왜냐하면, "현재까지 우리가 계산한 결과값에 의하면, 2원을 만드는데 필요한 동전의 최소갯수는

  2개가 필요하고, 이 2개에다가 '1원짜리 동전'을 추가적으로 할당함으로써 3원을 만들었기 떄문에, 결과적으로는

  총 3개의 동전이 필요하다."

  마찬가지로 ! 뒤에 나올 계산에 의하면, 3원은 '3원짜리 동전 1개만 사용'해서 만들 수가 있다.

  하지만 ! 우린 아직 3원을 계산하지 않았기 떄문에, 현재까지의 결과값에 의하면, 3원짜리 동전을 만드는데 필요한 동전의

  최소갯수는 3개라고 생각하자. F[3] = 3

4. 1원짜리 동전을 최종적으로 사용해서 4원 만들기.

- 위에서 말한 2원, 3원 만들기 과정을 잘 이해했다면, 이 경우 필요한 동전의 최소갯수는 '4'개가 된다는 것을

  알 수 있을 것이다.

여기까지 계산 결과값을 정리해보면..

F[1] = 1 , F[2] = 2 , F[3] = 3 , F[4] = 4 가 된다.

#Case2 : "2원짜리 동전을 최종적으로 사용"해서 1 ~ 4원 만들기.

1. 2원짜리 동전을 최종적으로 사용해서 1원 만들기

- 불가능하다. 동전이 지닌 가치가 애초에 1원보다 더 큰 가치를 가지고 있기 때문에, 동전을 쪼갤수도 없는 격이고, 이 경우는

  불가능하다.

2. 2원짜리 동전을 최종적으로 사용해서 2원 만들기

- 2원짜리 동전을 최종적으로 추가함으로써 2원을 만들어야 하는 상황이다. 그럼 기존의 상황은 어떤 상황이여할까 ??

  바로, "현재 0원을 가지고 있는 상황" 이여야 한다. 왜냐하면, 이 상황에서 2원짜리를 추가하면서 최종적으로 '2원'이 되기

  때문이다. 그럼 결과적으로 우리는 2원을 만드는데 필요한 동전의 최소갯수가 '1개' 라는 것을 알 수 있다.

  그런데 ! 우리가 기존에 계산했던 F[2]의 값은 '2'였다. 즉 ! 갱신이 필요한 상황이다.

  이 경우에는 F[2]의 값을 '1'로 갱신해주자. 왜냐하면 더 최소의 동전갯수가 나왔기 때문이다.

  F[2] = 1

3. 2원짜리 동전을 최종적으로 사용해서 3원 만들기

- 기존의 상황은 "현재 내가 1원을 가지고 있는 상황" 일 것이다. 이 상황에서 2원을 추가적으로 할당해줌으로써 3원을

  만들 것이기 때문이다. 1원을 만들 수 있는 동전의 최소갯수는 위에서 구한대로 F[1] = 1에 저장되어 있고,

  이 값을 통해서, F[3] = 2 라는 것을 계산할 수 있다. 왜 ? 1원을 만드는데 필요한 동전의 최소갯수는 1개이고, 여기에 2원

  짜리 동전 1개를 추가적으로 할당함으로써 최종적으로 2개의 동전이 필요하다는 것을 알 수 있다.

  또한, 기존의 F[3] 값인 '3'과 비교했을 때, 동전의 갯수가 더 줄어들었으므로, F[3] = 2로 갱신할 수 있다.

4. 2원짜리 동전을 최종적으로 사용해서 4원 만들기

- 마찬가지로 계산해보면, F[2] = 1이고, 이 상태에서 2원을 추가적으로 할당하는 상황이니, F[4] = F[2] + 1 = 2가 된다.

  이 역시, 기존의 F[4]값인 '4'보다 더 작은 값이니 갱신해 주어야 한다.

그럼 여기서 ! 이제 조금은 일반적인 상황을 생각해보자.

만약, 내가 X원짜리 동전을 최종적으로 사용함으로써, K원을 만들고 싶다면 어떻게 계산을 해줘야할까 ??

바로, "K - X원을 만들 수 있는 동전의 최소갯수 + 1" 을 해주면 되는 것이다. 왜냐하면, K - X원을 만드는데 필요한 동전의 최소갯수에다가 거기에 X원짜리 동전 하나를 추가적으로 할당해주면 결과적으로 K원을 만들 수 있기 떄문이다.

물론 ! 위에서 계산할 때, F[2] , F[3] , F[4]의 값에 갱신이 일어날 수가 있다. 즉 ! 기존에 구해놨던 동전의 최소갯수들과 비교했을 때 더 적은 동전의 갯수로 만들 수 있다면 이 값을 갱신해 주어야 한다는 것이다.

즉 ! 정리해보면..

F[K] = Min(F[K] , F[K - X] + 1) 이 된다는 것이다.

이를 점화식으로 문제를 해결할 수 있다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 110
using namespace std;
 
int N, K;
int Arr[MAX];
int DP[100010];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N >> K;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
}
 
void Solution()
{
    for (int i = 1; i <= K; i++) DP[i] = 2e9;
    for (int i = 1; i <= N; i++) DP[Arr[i]] = 1;
    DP[0] = 0;
    for (int i = 1; i <= N; i++)
    {
        for (int j = Arr[i]; j <= K; j++)
        {
            DP[j] = Min(DP[j], DP[j - Arr[i]] + 1);
        }
    }
 
    if (DP[K] == 2e9) cout << -1 << endl;
    else cout << DP[K] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}