백준 1450: 냅색문제 / C++
2023. 4. 3. 00:24ㆍ개인공부/코딩테스트
1450번: 냅색문제
첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다.
www.acmicpc.net
Meet in the middle 알고리즘을 배우는 문제로 투포인터를 응용한 개념을 이용하여 문제를 해결하였다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, C;
vector<int> vec;
vector<long long> Left;
vector<long long> Right;
int middle = N / 2;
void DpLeft(int index, long long sum)
{
if (index == middle){
Left.push_back(sum);
return;
}
DpLeft(index + 1, sum + vec[index]);
DpLeft(index + 1, sum);
}
void DpRight(int index, long long sum)
{
if (index == N) {
Right.push_back(sum);
return;
}
DpRight(index + 1, sum + vec[index]);
DpRight(index + 1, sum);
}
void Solve()
{
middle = N / 2;
int ans = 0;
DpLeft(0, 0);
DpRight(middle, 0);
sort(Left.begin(), Left.end());
sort(Right.begin(), Right.end());
auto right_index = Right.size() - 1;
// 투포인터를 다시 응용할 수 있지 않을까?
for (int i = 0; i < Left.size(); ++i)
{
if (right_index == -1)
break;
while (true)
{
if (Left[i] + Right[right_index] <= C) {
ans += right_index+1;
break;
}
--right_index;
if (right_index == -1)
break;
}
}
cout << ans;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N >> C;
for (int i = 0; i < N; ++i) {
int num = 0; cin >> num;
vec.push_back(num);
}
Solve();
}
|
cs |
'개인공부 > 코딩테스트' 카테고리의 다른 글
| 백준 20040번: 사이클 게임 / C++ (0) | 2023.04.03 |
|---|---|
| 백준 1717번: 집합의 표현 / C++ (0) | 2023.04.03 |
| 백준 1806번 : 부분합 / C++ (0) | 2023.04.02 |
| 백준 2470번 : 두 용액 / C++ (0) | 2023.04.01 |
| 백준 9660번 : 돌 게임 6 / C++ (0) | 2023.03.31 |