[백준 7450] Bin Packing (C++)

문제가 영어라 내가 이해한? 영어대로 해석해보겠다.

 

문제

1. 가방이 있고 물건이 있다.
2. 가방에는 최대 2개의 물건을 담을 수있다.
3. 가방의 용량을 넘어서는 물건을 담을 수 없다.

입력

1. 첫 번째 입력은 물건의 개수
2. 두 번째 입력은 가방의 용량

문제 해석

1. 물건의 무게가 큰 순서대로 정렬함.
2. 가방의 개수가 최소화되는 방법은 가장 큰 거를 우선 담고, 그 빈자리에 담을 수 있는 가장 작은 무게를 담는다. 
3. 만약 담았다면 담았던 물건은 제외시켜준다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int big(int i, int j)
{
    return i > j;
}
int N, W, totweight = 0;
vector<int> profit;
vector<int>include;
int Count = 0;
int bag = 0;
int main()
{
    cin >> N;
    cin >> W;
    profit.resize(N, 0);
    include.resize(N, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> profit[i];
    }
    sort(profit.begin(), profit.end(), big); //물건의 무게가 큰 순서대로 정렬함.
    int begin = 0;
    int end = N - 1;
    for (int i = 0; i < N; i++) 
    {
        for (int j = N-1; j >=0; j--)
        {
            if (profit[i] + profit[j]<=W) //가장 큰 무게와 가장 작은 무게를 담을 수 있다면 넣어줌.
            {
                bag++;
                N = N - 1; //담았다면 가장 끝에 꺼를 제외시켜야하기때문에 값을 하나 빼줌.
                break;
            }
            else if (profit[i] <= W) //만약 가장 큰 무게와 가장 작은 무게를 담을 수 없지만, 가장 큰 것만 담을수 있다면? 담아줌.
            {
                bag++;
                break;
            }
        }
    }
    cout << bag;
}

 

느낀 점 

한번 핀트를 잘못 잡으니까 문제를 해결하는데 굉장히 오래 걸렸다.

경우의 수를 잘못 계산했었다. 

하나씩 들어가는 경우의 수도 계산했어야 했는데 그걸 빼서 굉장히 애를 먹었다.