[필수 알고리즘] 그리디

개념

- 현재 차례의 최고의 답을 찾는 문제

- 어려운 이유 : 왜 그런지 증명하기가 어려움

- 예시 : 다른 금액의 동전이 여러개 주어졌을때 M원을 만드는 최소의 개수

 

아이디어

- 큰 금액부터 동전 차감

- 반례? : 동전의 개수가 무한대라서 없는 것으로 보임

- K를 동전 금액으로 나눈 뒤 남은 값을 갱신  

 

시간 복잡도

- for : N >O(N)

 

자료구조

- 동전 금액 : int[]

- 현재 남은 금액 : int

- 동전 개수 : int

 

문제풀이

- 백준 11047

 

1.

class num_11047
{
    static void Main(string[] args)
    {
        var sr = new StreamReader(Console.OpenStandardInput());
        var sw = new StreamWriter(Console.OpenStandardOutput());

        string[] input = sr.ReadLine().Split();
        int N = int.Parse(input[0]);
        int K = int.Parse(input[1]);


        List<int> coins = new List<int>();
        for (int i = 0; i < N; i++)
        {
            coins.Add(Convert.ToInt32(sr.ReadLine()));
        }

        coins.Reverse();
    }
}

- input값을 빠르게 받기위해 StreamReader와 StreamWriter로 받아온 후 

- 담은 coins를 Reverse하여 뒤집기

 

2.

int cnt = 0;
for (int i = 0; i < coins.Count; i++)
{
    cnt += K / coins[i];
    K = K % coins[i];
}

sw.WriteLine(cnt);
sw.Flush();
sw.Close();
sr.Close();

- 소수점이 담기지 않도록 int형으로 cnt을 선언 후

- K / coins[i]를 하여 나눠질때 cnt이 추가되고 K % coins[i]도 값이 생김

Ex)
1000값을 4200 나누면 cnt는 4가 되고 K % coins[i] = 200이 남는다.

K를 200으로 변경해준 후 K / coins[i]하여 K가 다 나눠질때까지 for문을 돌고 cnt를 불러오면 끝

*핵심은 큰 값부터 나눠야지 최솟값을 출력할 수 있다는 점!

 

최종코드

/*
1. 아이디어
- 동전을 저장한, 순서를 뒤집음
- 동전을 for하며 동전 사용 갯수 추가, 동전 사용한 만큼 K값 갱신

2. 시간복잡도
- O(N)

3. 자료구조
- 동전 금액 : int[]
- 동전 사용 : int
- 남은 금액 : int

*/


class num_11047
{
    static void Main(string[] args)
    {
        var sr = new StreamReader(Console.OpenStandardInput());
        var sw = new StreamWriter(Console.OpenStandardOutput());

        string[] input = sr.ReadLine().Split();
        int N = int.Parse(input[0]);
        int K = int.Parse(input[1]);


        List<int> coins = new List<int>();
        for (int i = 0; i < N; i++)
        {
            coins.Add(Convert.ToInt32(sr.ReadLine()));
        }

        coins.Reverse();
        int cnt = 0;
        for (int i = 0; i < coins.Count; i++)
        {
            cnt += K / coins[i];
            K = K % coins[i];
        }

        sw.WriteLine(cnt);
        sw.Flush();
        sw.Close();
        sr.Close();
    }
}

 

참고영상

- 바로가기