[백준] 11047 동전 0 풀이 (C++)

탐욕 알고리즘(Greedy algorithm)과 관련된 문제이다.

탐욕 알고리즘은 각 선택 과정에서 최적해를 찾아내는 알고리즘인데, 이 문제에선 필요한 동전 개수가 최소가 되게 하는 것이 최적이다.

따라서 가장 큰 동전들로 나눠주면 된다.

#include <iostream>
using namespace std;

int main(){
    int N,K;
    cin>>N>>K;
    int value[N] = {0,};
    for(int i=0;i<N;i++){
        cin>>value[i];
    }
	
    int answer = 0;
    int leftSum = K;
    for(int i=N-1;i>=0;i--){
        if(value[i] <= leftSum && leftSum != 0) {
            int tempNum = 0;
            tempNum = leftSum / value[i];
            answer += tempNum;
            leftSum = leftSum - (tempNum * value[i]);
        }
    }
	cout<<answer;
    return 0;
}

분명 예시들은 맞는데 이상하게 에러가 나서 봤더니, 배열 인덱스 시작을 고려안하고 for문을 적었다 ^^; 사소한 에러가 가장 힘들다..