(C++) - 백준(BOJ) 11256 : 사탕

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

11256번: 사탕

greedy문제였습니다.

📕 풀이방법

📔 입력 및 초기화

testcase, 사탕 수 candyNum, box 수 boxNum, sum, cnt, 상자를 입력받을 vector boxes를 선언 후 입력받습니다.

📔 풀이과정

1. boxes를 가로 * 세로가 큰 순으로 정렬해줍니다.2. 필요한 상자의 개수가 최소여야하므로 최대한 사탕을 담는것이 유리합니다. 가로 * 세로가 곧 사탕의 개수이므로 for loop를 수행하며 필요한 사탕의 개수 candyNum이상일 때까지 cnt++해줍니다.

📔 정답출력

cnt를 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int testCase, candyNum, boxNum, sum, cnt;
vector <pii> boxes;

bool cmp(pii a, pii b){
  return a.first * a.second > b.first * b.second;
}

int main(){
  cin >> testCase;
  while(testCase--){
    cin >> candyNum >> boxNum;
    sum = 0, cnt = 0;
    boxes.resize(boxNum);
    for(int i = 0; i < boxNum; i++) cin >> boxes[i].first >> boxes[i].second;

    sort(boxes.begin(), boxes.end(), cmp);

    for(int i = 0; i < boxNum; i++){
      sum += boxes[i].first * boxes[i].second;
      cnt++;
      if(sum >= candyNum) break;
    }
    cout << cnt << '\n';
  }
}