[C++] 백준 온라인 저지 동전 0 풀이

 

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

---

문제의 조건

 

1. 준규가 가진 동전의 개수 N, 만들어야 하는 금액 K가 주어진다. 

 

2. 둘째 줄부터 동전의 가치가 오름차순으로 주어지는데 

 i ≥ 2인 경우에 Ai는 Ai-1의 배수

 

---

풀이 과정

 

동전의 최솟값을 구해야 하니까 가지고 있는 금액 중 가장 큰 금액부터 빼 나가면 된다고 생각했습니다. 

그래서 그렇게 금방 코드를 짜고 예제도 통과가 잘 되고

반례도 통과가 잘 됐는데도 계속 틀렸다고 하는 것입니다. 

?????

모징...ㅠㅠ

 

또 한시간정도 게시판을 헤매다가 문제를 알게 되었습니다. 

 

전 처음에 준규가 가진 동전의 종류를 일일이 만들어줘야 하는 줄 알고 N만큼 반복문을 돌리면서 

직접 [1, 5, 10, 50, ...] 이런 식으로 넣어줬는데

알고 보니 저거도 다 입력을 받아야 하는 것 이었더라고요...ㅎ

문제에 저거에 대한 설명 좀 더 추가로 해 주시지...

 

그래서 최종적으로 통과한 코드 

 

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main(int argc, const char * argv[])
{
    int N, K;
    cin >> N >> K;
    
    vector<int> cashes;
    for (int i = 1; N >= i; i++)
    {
        int cash;
        cin >> cash; //여기도 내가 값을 넣는게 아니라 입력받는 것이었다...!!
        cashes.emplace_back(cash);
    }
    
    int answer = 0;
    //오름차순이라 가장 큰 금액은 맨 뒤에 있을 것이니까 인덱스 번호는 맨 뒤에서부터 감소시킨다. 
    int index = cashes.size() - 1; 
    while (0 < K)
    {
        //가장 큰 금액이 K원 보다 적으면 그만큼 감소시키고 동전 갯수 증가
        if (cashes[index] <= K)
        {
            int coins = K / cashes[index];
            answer += coins;
            K -= coins * cashes[index];
        }
        //아니면 그 다음으로 적은 금액 확인
        else
        {
            if (0 >= index)
                index = 0;
            else
                index--;
        }
    }
    
    cout << answer;
    
    return 0;
}