[Algorithm] BOJ11047 동전0 C#

BruteForceA·2023년 1월 13일
1
post-thumbnail

문제


입력 출력

입력
첫째 줄에 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.


예제


예제 입력 1

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 1

6

예제 입력 2

10 4790
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 2

12



풀이 및 코드

 // 동전 0 
    public class Boj11047
    {
        static void Main(String[] args)
        {
            List<int> intList = new List<int>();
            var nums = Console.ReadLine().Split().Select(int.Parse).ToArray();
            
            int n = nums[0];
            int k = nums[1];
            int money, result = 0;
            

            for (int i = 0; i < n; i++)
            {
                intList.Add(Convert.ToInt32(Console.ReadLine())); 
            }

            // 오름차순으로 정렬된 상태로 입력되기 때문에  최소값을 얻기위해 큰 수부터
            // 필터링 해야하므로 뒤집어준다.
            intList.Reverse();

            for (int i = 0; i < n; i++)
            {
                money = k / intList[i];

                if (money > 0)
                {
                    k -= money * intList[i];
                    result += money;
                }
            }

            Console.WriteLine(result);
            

        }
    }




출처

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

0개의 댓글