문제가 영어라 내가 이해한? 영어대로 해석해보겠다.
문제
- 가방이 있고 물건이 있다.
- 가방에는 최대 2개의 물건을 담을 수있다.
- 가방의 용량을 넘어서는 물건을 담을 수 없다.
입력
- 첫 번째 입력은 물건의 개수
- 두 번째 입력은 가방의 용량
문제 해석
- 물건의 무게가 큰 순서대로 정렬함.
- 가방의 개수가 최소화되는 방법은 가장 큰 거를 우선 담고, 그 빈자리에 담을 수 있는 가장 작은 무게를 담는다.
- 만약 담았다면 담았던 물건은 제외시켜준다.
코드
#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;
}
느낀 점
한번 핀트를 잘못 잡으니까 문제를 해결하는데 굉장히 오래 걸렸다.
경우의 수를 잘못 계산했었다.
하나씩 들어가는 경우의 수도 계산했어야 했는데 그걸 빼서 굉장히 애를 먹었다.
'CodingTest > Baekjoon' 카테고리의 다른 글
[백준 16563] 어려운 소인수분해 구하기 (C++) (0) | 2022.06.10 |
---|---|
[백준 1929]-소수구하기(C++) (0) | 2022.06.09 |
[C++] 백준 1978 - 소수 찾기 (0) | 2022.06.01 |
[C++] 백준 1037 - 약수 (0) | 2022.06.01 |
[백준 C++] 1003 (피보나치 함수) (0) | 2022.05.03 |