[HackerRank] Mark and Toys

1주차 자유문제
Practice > Algorithms > Greedy

풀이

최대한 많은 선물을 사기 위해 적은 값의 선물부터 골라야 한다고 생각했다. 따라서 prices 백터를 STL sort를 사용하여 정렬해 주었다.

// sort 함수는 오름차순이 기본이다. 
//내림차순으로 정렬하고자 할땐, 비교함수를 사용해야 한다.
sort(prices.begin(), prices.end());

이후 순차적으로 선물의 가격이 남은 돈보다 작다면 선물을 선택하는 방식으로 문제를 해결하였다.

전체적인 코드는 다음과 같다.

int maximumToys(vector<int> prices, int k) {
    int cnt = 0;
    
    sort(prices.begin(), prices.end());
    for(int i=0; i<prices.size(); i++){
        if(k < prices[i]) break;
        ++cnt;
        k -= prices[i]; 
    }
    
    return cnt;
}

모든 예제도 다 통과하였다.