(11047) 동전 0

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

단계별로 풀어보기

23단계(그리디 알고리즘) 1번째

 

 

 

그리디 알고리즘은 각 단계에서 눈앞의 최적의 상황만 선택해 전체 답을 구하는 기법이다.

보통 그리디 알고리즘이 성립하기 위해서는 아래 두 가지 조건을 만족시켜야 한다.

1) 각 단계는 독립적이라 이전 선택이 이후 선택에 영향을 주지 않음

2) 전체 문제의 최적해가 부분 문제의 최적해로 구성되어 있어야 함

그리디 알고리즘의 장점은 각 단계마다 눈앞의 상황만 고려하면 되기 때문에 코드를 짜기 상대적으로 쉽고 답을 구하는 시간이 빠르다는 점이다.

 

개념 말고 이 문제에 대해 살펴보면, 평범한 거스름돈 문제지만 각 동전들은 배수 관계라는 특별한 조건이 있다.

단위가 x인 동전과 xn인 동전이 있다면, x동전을 n개 이상 쓰는 시점부터는 이를 그냥 xn동전 하나로 치환하는 것이 항상 이득이다.

즉 이 문제는 가장 가치가 높은 동전부터 탐색해 이 동전으로 낼 수 있는 만큼 내는, 각 동전마다 최적해를 구하는 방식으로 풀면 답이 나온다.

물론 DP로도 풀 수 있지만, 그리디 알고리즘에 비해 시간이 더 오래 걸릴 것이다.

 

 

 

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

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, k;
  
  cin >> n >> k;
  
  vector<int> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i];
  
  int ans= 0;
  
  for(int i=n-1;i>=0;i--){
    ans+= k/v[i];
    k%= v[i];
  }
  
  cout << ans;
  
  return 0;
}