백준 11047 동전0 C#

그리디 알고리즘 중 가장 첫번째 스탭이었는데 사실 그리디 알고리즘이 먼지도 모르고 그냥 단순한 생각대로 풀었다.

 

그리디 알고리즘 (탐욕 알고리즘)

최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.  

 

using System;

namespace c_bjcoding
{
    class MainClass
    {
        public static void Main(string[] args){
            int count = 0;
            string[] input = Console.ReadLine().Split(' ');

            int num =int.Parse(input[0]);
            int target_value = int.Parse(input[1]);

            int[] values = new int[num];

            for (int i = 0; i < num; i++){
                values[i] = int.Parse(Console.ReadLine());
            }
            while(target_value != 0){
                for (int j = num-1; j >= 0 ;j--){
                    if(target_value - values[j] >= 0){
                        target_value -= values[j];
                        count++;
                        break;
                    }
                }   
            }
            Console.WriteLine(count);
        }
    }
}

 

최종합에서 가장 큰 단위 부터 빼나가는 식으로 구현하였다. 

끝