백준 7450: Bin Packing [C/C++]

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

7450번: Bin Packing

코드:

#include <iostream>
#include <algorithm>
using namespace std;
int item[111111];
int n, bin;
int main(void) {
    cin >> n;
    cin >> bin;
    for (int i = 0; i < n; i++) cin >> item[i];
    sort(item, item + n);
    int l = 0, r = n - 1, cnt = 0;
    while (l <= r) {
        if (item[l] + item[r] <= bin) l++;
        r--;
        ++cnt;
    }
    cout << cnt;
    return 0;
}

---

그리디 증명:

Bin에는 2개까지 들어가므로 가능하다면 1개보다 2개를 담는 것이 낫습니다.

그리고 Bin에 담기지 않은 item은 최대 값과 최소 값을 합쳐야, 최대 값을 제거할 때 item[l] + item[r] <= bin일 확률이 가장 높으므로 그리디가 성립합니다.

---

풀이:

정렬 후 투 포인터 알고리즘을 이용합니다.