https://www.acmicpc.net/problem/1450
문제
세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.
N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 10^9보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다.
출력
첫째 줄에 가방에 넣는 방법의 수를 출력한다.
최대 30가지가 나오므로 물건 하나하나 넣을지 안 넣을지를 결정하면 2^30 이 걸려 시간이 초과가 된다. 그러므로 반을 나누어 왼쪽에서 K 만큼 썼다면 오른쪽에서는 C-K 보다 적게 쓴 경우 알맞은 경우의 수가 된다. 왼쪽과 오른쪽에서 무게와 선택한 개수에 상관없이 선택한 물건들의 무게의 총합을 각각의 벡터에 추가한다. 이제 오른쪽 벡터를 정렬하고 왼쪽 벡터를 순회하며 왼쪽 벡터의 원소가 K 인 경우 오른쪽 원소가 C-K 보다 작은 경우를 추가하면 된다. 이때 벡터가 굉장히 크므로 linear 하게 순회하면 안 되고 upper_bound()를 활용하여 O(logN)의 시간에 K 보다 큰 원소의 위치를 찾아 그 인덱스를 더하면 해결할 수 있다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, C;
long long arr[31];
long long cnt=0;
vector<long long> left_sum;
vector<long long> right_sum;
void left(long long s,long long sum) {
if (s == N/2) {
left_sum.push_back(sum);
return;
}
left(s + 1, sum);
left(s + 1, sum + arr[s]);
}
void right(long long s, long long sum) {
if (s == N) {
right_sum.push_back(sum);
return;
}
right(s + 1, sum);
right(s + 1, sum + arr[s]);
}
int main() {
cin >> N >> C;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
left(0, 0);
right(N / 2 , 0);
sort(right_sum.begin(), right_sum.end());
for (int i = 0; i < left_sum.size(); i++) {
cnt += upper_bound(right_sum.begin(), right_sum.end(), C - left_sum[i]) - right_sum.begin();
}
cout << cnt;
}
처음 문제를 보고 저번 문제와 동일하다고 생각하여 풀었다. 하지만 다른점은 저번에는 key 값이 1'000'000 이 최댓값이었고 이번에는 1'000'000'000이 최대였으며 해당 key 값의 value만 더하는 것이 아니라 주어진 key값보다 작은 value의 값을 모두 더해야 했다. map 에도 upper_bound 가 있지만 iterator 만으로는 map에 key보다 작은 값들이 몇 개가 존재하는지 알기는 어려웠다. 따라서 vector를 이용하여 upper_bound - begin을 활용하여 값을 더해야 시간 안에 들어올 수 있었다. 처음에는 문제를 너무 쉽게 풀 것 같다는 생각을 했지만 저번 문제보다 추가적인 부분이 존재했다. 상당히 아쉬움이 남는 문제였다!
'코딩 > 백준' 카테고리의 다른 글
[백준] 1508번 레이스 - C++ (0) | 2022.08.14 |
---|---|
[백준]1561번 놀이기구 - C/C++ (0) | 2022.08.11 |
[백준]2110번 공유기 설치 - C++ (0) | 2022.08.08 |
[백준]1208번 부분수열의 합 2 - C++ (0) | 2022.08.06 |
[백준]1253번 좋다 - C++/Java (2) | 2022.08.05 |