백준 11047번 - 동전 0 (C#)

김보근·2025년 7월 29일

C#백준

백준

목록 보기

50/62

백준 11047번 - 동전 0 (C#)

오늘은 백준 11047번 "동전 0" 문제를 C#으로 풀었다.
처음엔 단순히 작은 동전부터 더해가면서 K원을 만들려고 했는데, 문제의 핵심은 "동전 개수를 최소로" 만드는 것이었다.

https://www.acmicpc.net/problem/11047

문제 요약

N개의 동전 종류가 주어지고, 각 동전은 무한히 사용 가능하다.
목표 금액 K원을 만들기 위해 가장 적은 개수의 동전을 사용하는 것이 목표다.

내가 처음 접근한 방식

while(output < k)
{
    for (int i = 0; i < list.Count; i++)
    {
        output += list[i];
        count++;
    }
}

→ 하지만 이건 단순히 작은 동전부터 계속 더해가는 방식이라
동전 개수를 최소로 만들 수 없다는 단점이 있다.

해결 방법 (Greedy)

가장 큰 동전부터 최대한 많이 사용하는 방식으로 접근해야 최소 개수가 나온다.

동전을 내림차순 정렬한다.
현재 금액 K보다 작거나 같은 가장 큰 동전을 선택해 최대한 많이 사용한다.
남은 금액 K를 갱신하고 반복한다.

작성한 코드

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace backjoon
{
    internal class Program
    {
        static void Main()
        {
            string[] input = Console.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(int.Parse(Console.ReadLine()));
            }

            coins.Sort((a, b) => b.CompareTo(a)); // 한 줄로 내림차순 정렬


            int count = 0;

            foreach (int coin in coins)
            {
                if (coin <= k)
                {
                    count += k / coin;
                    k %= coin;
                }
            }

            Console.WriteLine(count);
        }
    }
}

배운 점

동전 문제는 그리디 알고리즘으로 풀 수 있다.
입력이 이미 오름차순으로 주어진다면 Sort() 없이 Reverse()만 써도 된다.
하지만 입력이 오름차순이라는 보장이 없다면 반드시 Sort() 후 Reverse()를 하거나 Sort((a, b) => b.CompareTo(a))로 내림차순 정렬해야 한다.
정렬이 잘못되면 동전을 비효율적으로 사용해 잘못된 결과가 나올 수 있다.