[Algorithm] Baekjoon 11047번 : 동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int input = 0;
    int targetMoney = 0;
    vector<int> coins;
    int answerCount = 0;
 
    cin >> n >> targetMoney;
 
    for (int i = 0; i < n; i++)
    {
        cin >> input;
 
        coins.push_back(input);
    }
 
    for (int i = coins.size()-1; i >= 0; --i)
    {
        if (targetMoney % coins[i] != 0)
        {
            answerCount += (targetMoney / coins[i]);
            targetMoney %= coins[i];
        }
        else
        {
            answerCount += (targetMoney / coins[i]);
            break;
        }
    }
 
    cout << answerCount;
}

 

그리디를 활용한 기본적인 동전개수구하기 문제.

 

저 코드로만해서 답이 구해지는건, 주어지는 동전크기가 이전 동전크기의 배수라서 가능한 것 같다.

 

만약 그런 조건이 없다면, 아마 저 코드로는 안풀릴것이다.

 

타겟이 1600이고, 동전이 각각 300, 800, 1000이 주어진다면 저 코드로는 풀리지 않는다.

 

올바른답은 800짜리 2개 사용하는게 맞지만, 위 코드로하면 1000짜리 1개, 300짜리 2개해서 총 3개가 답으로 나오기 때문이다.