[백준 - C#] 11047 동전 0

문제링크

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

11047번: 동전 0

 

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다.
이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

조건

시간제한 : 1초
메모리 제한 : 256 MB

입력

첫째 줄에 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의 값을 만들 수 있는 동전 개수의 최솟값을 구하는 문제 입니다.

동전 갯수의 최솟갑을 구하려면 큰 동전 부터 누적시키는게 좋다고 생각이되어 동전의 큰 수부터 작은 수로 반복을 했으며, 몇가지 조건문을 이용하여 동전을 누적하고 갯수를 추가하였습니다.

 

첫 번째로 처음 반복문을 시작하면 동전의 값이 K 값보다 클 수 있고 누적된 값에 더해줘도 값이 클 수 있다고 생각하여 

(K < sum + money[i]) 조건문을 추가하였습니다.

 

두번째로 while 문 안에서 반복적으로 같은 동전을 누적시켜주다가 K 값보다 크게되면 반복문을 빠져나오도록 추가하였습니다. 

(sum + money[i] > K)

 

요즘 그리디 알고리즘 문제에 대해 풀고 있는데, 매번 동전을 더해주는 최적의 값을 찾는거라고 봐도 되는지, 아직까지는 확신이 서지 않습니다. 더 열심히 그리드 알고리즘 문제를 풀어봐야 알 것 같습니다. !!

C# 코드

static void Main(string[] args)
{
    // 11047 그리디 알고리즘
    StreamWriter writer = new StreamWriter(OpenStandardOutput());
    StreamReader reader = new StreamReader(OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
    int N = int.Parse(input[0]); // 동전의 총 N종류
    int K = int.Parse(input[1]); // K 가치의 합
 
    int[] money = new int[N];
    int sum = 0; // 동전을 더해주기 위해서 필요한 변수
    int count = 0; // 동전의 개수
 
    for (int i = 0; i < N; i++)
        money[i] = int.Parse(reader.ReadLine());
 
    for (int i = N - 1; i >= 0; i--) // 동전의 큰 수부터 작은 수로 반복
    {
        if (K < sum + money[i]) // 더해줬을 때 값이 K보다 크다면 그거 보다 적은 동전으로 
            continue;
 
        while (true)
        {
            if (sum + money[i] > K) // 더해줬을 때 값이 K 보다 크다면 반복문 종료
                break;
 
            sum += money[i]; // 동전 누적
            count++; // 동전 갯수 추가
        }
 
        if (sum == K) // 누적된 동전이랑 K랑 같다면 이제 그만 끝
            break;
    }
 
    writer.WriteLine(count);
 
    writer.Close();
    reader.Close();
}

 

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.