티스토리 뷰

알고리즘

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

J3SUNG 2019. 1. 29. 19:18

 

N개의 동전 종류가 있을 때 동전들을 합하여서 K라는 값을 최소한의 동전을 이용해서 만드는 문제입니다.

 

입력되는 수들이 오름차순으로 주어지기 때문에 큰값들부터 비교를 해서 

찾는 값 K 보다 작으면서 가장 큰 값 v[i]를 value가  K를 넘지 않을때 까지 더합니다. 이와 동시에 카운트를 해줍니다.

이와 같은 과정을 반복하여 총 몇번의 카운트를 통해서 값을 찾을 수 있는지 확인할 수 있습니다.

 

K보다 작은 가장 큰값들을 더해서 최소의 횟수를 찾았습니다.

이와 같은 알고리즘을 그리디 알고리즘이라고 합니다.

 

#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char * argv[])
{
   int N;
   int K;
   int x;
   int value = 0;
   int count = 0;
   vector<int> v;

   cin >> N;
   cin >> K;

   for (int i = 0; i < N; i++) {
      cin >> x;
      v.push_back(x);
   }
   
   for (int i = N-1; 0 <= i; i--) {
      while(v[i] < K && value + v[i] <= K) {
         value += v[i];
         count++;
      }
   }

   cout << count << endl;

   return 0;
}
728x90

'알고리즘' 카테고리의 다른 글

[C++] 백준 1001번 A-B  (0) 2019.03.04
[C++] 백준 1000번 A+B  (0) 2019.03.04
[C++] 백준 2557번 Hello World  (0) 2019.03.04
[C++] 백준 2839번 설탕 배달  (0) 2019.02.05
[C++] 백준 9095번 1,2,3 더하기  (0) 2019.02.03
[C++] 백준 11047번 동전 0  (0) 2019.01.29
댓글
댓글쓰기 폼
공지사항