[백준] 11047번 동전 0 C++ 풀이

12​

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

---

알고리즘 분류

• 그리디 알고리즘

---

문제 설명

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

---

예제 입력

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

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

---

예제 출력

6

12

 

---

아이디어

동전은 종류 별로 매우 많이 가지고 있으니까 가장 단위가 큰 동전부터 k에서 빼고 동전의 개수를 세다 단위가 작은 쪽으로 이동하다가 k가 0이 되는 순간의 개수를 출력하면 된다.

---

알고리즘

각 동전을 배열에 담고 배열의 역순으로 만약 동전의 가격이 k보다 작거나 같다면 count를 1 증가시키고 k에서 동전의 가격만큼을 뺀다. 이를 k가 0이 될 때까지 반복하다가 k가 0이 되는 순간에 출력하면 정답이다.

---

코드

#include <iostream>
using namespace std;
int main() {
    int n,k,cnt=0;
    cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    for(int i=n-1;i>=0;i--)
        {
            while( arr[i] <= k)
            {
                k -= arr[i];
                cnt++;
            }
            if(k==0) break;
        }
    cout<<cnt;
    return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/11047

이러한 종류의 그리디 알고리즘을 사용하는 문제는 전에도 꽤나 풀어봤던 기억이 있었다.

그래서 비교적 쉽게 코드를 짤 수 있었다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!