[백준 11256번] 사탕 (C++)

문제링크 : https://www.acmicpc.net/problem/11256

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int T, J, N;
int arr[10001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> T;

    while(T--)
    {
        int cnt = 0; //상자 갯수
        cin >> J >> N;
        for(int i=0; i<N; i++)
        {
            int r, c;
            cin >> r >> c;
            arr[i] = r*c; //크기 저장
        }

        sort(arr, arr+N, greater<>()); //내림차순 정렬

        for(int i=0; i<N; i++)
        {
            J-=arr[i]; //상자에 사탕 넣기
            if(J<=0) //모두 넣은 경우
            {
                cnt++; //카운팅하고 종료
                break;
            }
            cnt++; //카운팅
        }

        cout << cnt << "\n";
    }

    return 0;
}

 

그리디한 정렬문제이다.

먼저 상자의 크기를 구해서 배열에 따로 저장하고, 해당 배열을 내림차순으로 정렬해준다.

 

이러면 상자 크기가 가장 큰 값(사탕을 제일 많이 담는 순서)으로 정렬되는데,

총 사탕 갯수인 J에서 배열의 값을 빼주며 남은 사탕 갯수를 체크하면 된다.

만약 사탕 갯수가 0이하라면 사탕을 무사히 모두 넣은 것이므로 카운팅 후 종료하고,

아직 사탕 갯수가 남았다면 계속하여 카운팅한다.

 

이렇게 카운팅한 값을 매 테스트케이스마다 출력해주면 된다.