[백준] 11047번

그리디 알고리즘으로 푸는 문제로 제일 큰 값부터 값을 줄여나가면서 나누면서 최소로 필요한 개수를 구하는 방법을 썼다. target값의 범위를 같거나 작게해서 풀어야하는데 그 부분을 인지 못하고 작게만 해서 엄청틀렸다..!

 

 

#include <iostream>
using namespace std;

int main(){
    int numberofcoin;
    int target;
    int i;
    int count=0;
    cin>>numberofcoin>>target;

    int *arr=new int[numberofcoin];

    if(numberofcoin<1 || numberofcoin>10 ||target <1 || target>100000000)
        return 0;

    for(i=0;i<numberofcoin;i++){
        cin>>arr[i];
        if(arr[i]<1 || arr[i]>1000000)
            return 0;
    }

    for(i=numberofcoin-1;i>=0;i--){
        if(arr[i]<=target){
            count+=target/arr[i];
            target%=arr[i];
            if(target==0)
                break;
        }

    }

    cout<<count<<endl;

}
​