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

문제

n가지 종류의 동전으로 가치 합이 k가 되도록 함 (1 <= n <= 100, 1 <= k <= 10,000)

동전 개수를 최소화 하도록 하여 가치 합이 k가 되도록 함

동전 무제한 사용 가능, 가치가 같은 동전이 여러번 주어 질 수 있다

 

입력

n k

n1

n2

...

nn

 

예제 입력

3 15

1

5

12

 

출력

3

---

 

문제 분석

처음에 보았을 땐, 그리디 문제인 줄 알았다. 그러나 좀 고민을 하다보니, 그리디로 풀 수 있을까? 라는 생각이 들었고, 아무리 생각해도 방법이 안 나왔다.

이전 문제가 DP(Dynamic Programming)인 점을 생각하면, 이번 문제 또한 비슷한 것임을 알 수 있다... 하지만 이렇게 하면 안 되겠지..? ㅠㅠㅠ

문제의 포인트

1. 같은 가치의 동전 입력 가능 -> 중복 제거 필요 (입력단에서

2. 최소 개수가 되는 방법 찾아서, 동전 개수 저장

IDEA

1. k값 보다 큰 값은 저장 X

2. 점화식 만들자! -> 1원 만드는 방법부터 ~ 1만원 만드는 방법까지

 

이를 통해 코드를 작성했고, 정답이었다!

#define MAX_DATA_NUM 10010
#include <iostream>

using namespace std;

int used_coins[MAX_DATA_NUM];

int n, k;

int main()
{
    //INIT
    for(int i=0; i<MAX_DATA_NUM; ++i)
    {
        used_coins[i] = -1;
    }

    //INPUT
    cin >> n >> k;
    for(int input_step = 1; input_step <= n; ++input_step)
    {
        int input_number;
        cin >> input_number;
        for(int count_number = input_number; count_number<=k; ++count_number)
        {
            //만약 입력 값이 count_number와 정확히 같은 값이라면, 그 값은 무조건 1
            if(input_number == count_number)
            {
                used_coins[count_number] = 1;
            }
            //만약 count_number값에서 현재 input_number를 뺀 값이 -1이 아니라면, -> if(used_coins[count_number - input_number] != -1)
            //used_coins[count_number]에 들어갈 값은 used_coins[count_number - input_number] + 1 -> 만약 그 값이 더 작은 경우만!
            else if(used_coins[count_number - input_number] != -1)
            {
                if(used_coins[count_number] == -1)
                {
                    used_coins[count_number] = used_coins[count_number - input_number] + 1;
                }
                else
                {
                    used_coins[count_number] = (used_coins[count_number] < used_coins[count_number - input_number] + 1) ? 
                        used_coins[count_number] : used_coins[count_number - input_number] + 1;
                }
            }
        }
    }
    // for(int i=0; i<=k; ++i)
    // {
    //     cout<< i << "th : " << used_coins[i] << '\n';
    // }
   cout<<used_coins[k];

}

코드 과정 설명

1. used_coins -> 해당 배열 위치의 값을 만드는데 필요한 동전의 개수를 저장하는 배열

   그러므로, used_coins[1] 은 1원의 값어치를 만드는데 필요한 코인 갯수이다.

2. '입력한 값' 원이 들어왔으면 '입력한 값' 원을 만드는 최소한의 동전 개수는 그 동전만 쓰면 되므로, used_coins['입력한 값' ] = 1와 같이, '입력한 값' 에 해당하는 배열은 1로 초기화 해준다.

3-1. 만약 used_coins[현재 보는 중인(count_number) 값 - 현재 입력된 값(input_number)] == -1 -> 이 경우는 이전에도 만들 수 없었으니, 지금도 만들 수 없다는 것을 의미함, 유지 필요

3-2. 위의 used_coins[...] != -1  -> 이 값은 만들 수 있다는 것을 의미하므로, 계산할 수 있다!

4. 계산 가능한데, 이전 값과 비교하여 어떤게 더 큰지 비교해서 더 작은 값을 넣어주어야 함! -> 3항 연산자로 바로 계산하려고 했으나, 예외처리가 필요했음.. ㅠㅠㅠ

4-1. 예외처리 -> 이전 결과가 -1인 경우, 그냥 값을 갱신

4-2. dp[n원] = (dp[n원 만드는 방법] VS dp[n원 - 현재 입력된 값] + 1) 해서 더 작은 값 넣어서 갱신하기!

---

 

 

[문제 후기]

확실히 어떤 방식으로 풀어야 하는지, 그리고 어떤 방식인지 유사 문제를 풀어보니 쉽게 접근할 수 있었다. 결국 발상의 문제인데.. 그 발상을 하는 게 제일 어려운 것 같다는 생각이 무럭무럭...

그리고 코드 리뷰를 하면서 든 생각으로, 다음과 같은 예외처리와 코드 리팩토링을 하는게 맞았을 것 같다는 생각이 든다.

1. 입력 중복 예외처리

2. 입력 작은 숫자 순서대로 Sorting

3. -1을 입력하는 게 아닌, 가치의 최대값을 입력해서 예외처리 하기 (더 작은 값을 비교해서 넣기 때문에...)

 

다음에는 이런 예외 처리를 하기 위해 어떤 방식을 쓸까 고민하는 시간으로, 딕셔너리도 찾아볼까 생각 중이다. (입력 중복 예외처리에 용이할 것 같아서!)

 

그래도 풀었으니, 기분은 좋다 ㅎ