notGreedy

notGreedy.cpp

#include <iostream>
using namespace std;

const int INF = 1e7;
const int N = 6;

int main()
{
    int use1, use3, use4;
    int minUse = INF;

    for(int a=0; a<=N; a++) 
    for(int b=0; 3*b<=N; b++) 
    for(int c=0; 4*c<=N; c++) 
        if(1*a + 3*b + 4*c == N)
            if(a+b+c < minUse) {
                minUse = a+b+c;
                use1 = a;
                use3 = b;
                use4 = c;
            }
    
    cout << "1을 사용한 횟수: " << use1 << "\n";
    cout << "3을 사용한 횟수: " << use3 << "\n";
    cout << "4을 사용한 횟수: " << use4 << "\n";
    cout << "사용한 동전의 총 개수: " << minUse << "\n";

    return 0;
}