CHANGE

Algospot

CHANGE

Haeine 2017. 8. 28. 21:21

<문제 링크>

https://algospot.com/judge/problem/read/CHANGE

문제

Sue is waiting in line at the grocery store. Being in a hurry, she wants to pay with exact change when she gets to the front of the line. However, she does not know how much her items are going to cost; instead, she only knows an upper bound C on their total cost. Given a list of the various coins Sue has in her pocket, your goal is to determine the minimum number of coins she must take out in order to ensure that she can make exact change for every amount from 1 to C.

입력

The input test file will contain multiple cases. Each test case begins with a single line containing two integers C (where 1 ≤ C ≤ 1000000000) and m (where 1 ≤ m ≤ 1000), where C is the maximum amount for which Sue must be able to make change, and m is the number of unique coin denominations Sue has in her pocket. The next m lines each contain two numbers, vi (where 1 ≤ vi ≤ 1000) and ni (where 1 ≤ ni ≤ 1000), where vi is the value of the ith coin denomination, and ni is the number of coins of that denomination that Sue has in her pocket. Input is terminated by a single line containing the number 0; do not process this line.

출력

For each test case, either print a single line containing the number of coins Sue must use in order to make exact change for all amounts up to C, or print “Not possible” if exact change cannot always be made with any combination of coins in Sue’s pocket.

위 문제 링크로 가보면 문제의 제한시간은 1초이다. c가 1억이라는 상당히 큰수에 비해 문제를 해결하는 시간이 굉장히 짧다는걸 고려했을때 본 문제는 그리디(탐욕) 알고리즘으로 해결 가능 할 가능성이 높다고 봤다. 그래서 어떻게 하면 그리디하게 문제를 해결할 수 있을까를 고민해본 결과 아래와 같은 로직을 생각해 낼 수 있게 되었다.

현재 1 ~ i 까지 의 모든 숫자들의 계산이 가능한 동전의 집합을 구해 놓은 상태라고 하자. 이때 i + 1을 계산 할 수 있으려면 1 ~ i + 1 범위내의 가치를 갖는 동전이 필요하다. 이유는 간단하다 만약 가치가 i + 1인 동전이 있다면 동전 한개로 계산이 가능할 것이고 가치가 i을선택한다면 이미 선택되어진 동전에서 가치가 1인 동전과 함께 계산하면 된다. 또한 가치가 1인 동전을 선택한다면 지금까지 선택되어진 동전의 총합이 i이므로 동전 모두를 내면 된다. 이렇게 동전을 선택하고 나면 다음은 i + 2를 계산하기 위한 조합을 구할 필요가 없다. 우리가 i + 1을 계산하기 위한 동전을 구하기 위해서 선택한 동전의 가치가 k라고 가정한다면 우리는 k + 1 ~ k + i 까지의 모든 가격을 계산할 수 있다. 그 이유는 간단한것이 1 ~ i 까지 계산 가능한 동전의 집합에 가치가 k인 동전이 추가되었다고 생각하면 쉽게 이해가 된다. 그렇다면 우리가 다음 으로 고려해야할 계산금액은 i + k가 된다. 이와같은 그리디한 로직을 코드로 구현하면 아래와 같다.

int c, m;

int main() {
while (true) {
  cin >> c;
  if (c == 0) return 0;
  cin >> m;
  vector<pair<int, int> > coins;
  for (int i = 0; i < m; ++i) {
   int cVal, cNum;
   cin >> cVal >> cNum;
   coins.push_back(make_pair(cVal, cNum));
  }
  sort(coins.begin(), coins.end());
  reverse(coins.begin(), coins.end());
  vector<pair<int, int> > repository;
  int sum = 0;
  int ret = 0;
  bool notPossible = false;
  while (sum < c) {
   while (!coins.empty() && coins.back().first <= sum + 1) {
    repository.push_back(coins.back());
    coins.pop_back();
   }
   if (repository.empty()) {
    cout << "Not possible" << endl;
    notPossible = true;
    break;
   }
   sum += repository.back().first;
   --repository.back().second;
   ++ret;
   if (repository.back().second == 0)
    repository.pop_back();
  }
  if(!notPossible)
   cout << ret << endl;
}
}