BAEKJUN 11047번 [C#] 동전 0 그리고 DateTime

그리디 알고리즘 SILVER 4

동전 0

 

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

 

생각

그리디 알고리즘은 효율상관없이 되는대로 실행하면 되는거로 알고있다.

높은 단위부터 K에 뺄셈연산해서 양수나 0이 나오면 연산횟수를 늘리고 K가 0이 될 때까지 반복하자.

 

제출코드

public class CodingTest
{
    public static void Main()
    {
        Console.WriteLine(Greedy());

        int Greedy()
        {
            // 입력부

            string NandK = Console.ReadLine();
            string[] ss = NandK.Split(' ');
            int N = int.Parse(ss[0]);   // 종류
            int K = int.Parse(ss[1]);

            int calculateCount = 0;

            int[] inputNs = new int[N];
            for(int i =0; i < N; i++)
            {
                inputNs[i] = int.Parse(Console.ReadLine());
            }
            // 입력부 끝
            
            // 구현
            while (K != 0)
            {
                for (int i = inputNs.Length - 1; i >= 0; i--)
                {
                    if (K == 0) return calculateCount;
                    else if (K - inputNs[i] >= 0)
                    {
                        K -= inputNs[i];
                        calculateCount++;
                        break;
                    }
                    // Console.Write(K); Console.WriteLine(" " + calculateCount);
                }
            }
            return calculateCount;
        }
    }
}

 

 

// 소감

내 코드의 실행시간은 164ms인데 다른 사람이 한 코드는 64ms가 나온걸 보니 어떤 부분이 다른지 살펴봤는데

for(int i = 0; i < n; i++)
{
    if((k/value[i]) >= 1)
    {
        //Console.WriteLine($"{value[i]}원");
        result += k/value[i];
        k = k%value[i];
    } 
}

K의 값을 같은 i에서 뺄셈하는 횟수를 나눗셈의 몫으로 한 번에 얻어냈다.

 

 

 

 

관련 링크

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전

그리디 알고리즘 - 나무위키 (namu.wiki)

그리디 알고리즘

Greedy Algorithm(그리디 알고리즘) 개념, 추천 문제 (tistory.com)

Greedy Algorithm(그리디 알고리즘) 개념, 추천 문제

 

 

// DateTime

[백준] C# : 오늘 날짜 (10699번) (velog.io)

[백준] C# : 오늘 날짜 (10699번)