[C++] BOJ 11256 사탕

www.acmicpc.net/problem/11256

11256번: 사탕

코드

#include<iostream>
#include<algorithm>
using namespace std;

int t, j, n;
int box[1005];
int main() {
	cin >> t;

	while (t--) {
		cin >> j >> n;
		int a, b;
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			cin >> a >> b;
			box[i] = a * b;
		}
		sort(box, box + n);
		for (int i = n - 1; i >= 0; i--) {
			if (j >= box[i]) {
				j -= box[i];
				cnt++;
			}
			else if (j > 0) {
				cnt++;
				cout << cnt << '\n';
				break;
			}
			else{
				cout << cnt << '\n';
				break;
			}
		}
	}
}

풀이방법

간단한 그리디문제다. 크기가 큰 박스부터 차례대로 채우면 된다.

각 박스의 크기를 배열box에 저장해주고, 크기순으로 배열한다. for문을 이용해서 크기가 큰 박스부터 사용해 남은 사탕의 개수와 비교하고, 사탕을 넣어준다. 남은 사탕이 없으면 상자의 개수를 출력해준다.

고민과정

출력과정을 더 깔끔하게 만들 수 있을 것 같기도 하다.