This is my Life :: SRM 415 DIV2 250 CollectingUsualPostmarks

SRM 415 DIV2 250 CollectingUsualPostmarks

TopCoder 2008/09/03 20:55

이번 문제는 내가 지금까지 풀어본 TopCoder 문제 중에서 가장 쉽게 풀었던 문제였던것 같다

parameter가 두가지 주어진다
prices와 have
prices는 각 우표의 가격을 나타내고
have는 이 중에서 자신이 가지고 있는 우표를 나타낸다

return value는 현재 자신이 가지고 있는 우표를 돈으로 바꿔서 최대한 많은 종류의 우표를 샀을때
몇개의 우표를 가질 수 있는지를 넘겨주면 된다.

#include <vector>
#include <algorithm>

typedef unsigned int uint;

using namespace std;

class CollectingUsualPostmarks {
public:
int numberOfPostmarks(vector <int> prices, vector <int> have) {
   int rr = 0;
   int cash = 0;
   uint i;

   // Exchange
   for(i=0 ; i<have.size() ; i++) {
cash += prices[ have[i] ];
   }

// Purchase
sort(prices.begin(), prices.end());

   for(i=0 ; i<prices.size() ; i++) {
cash -= prices[i++];

if(cash<=0) {
   return rr;
}
rr++;
   }

return rr;
}
};