Coding_Test 연습/SWEA
[SWEA] (C++) D4 1486. 장훈이의 높은 선반
Codetesing
2022. 4. 12. 04:27
크게 어렵지않은 완전탐색 문제이다.
DFS를 사용해서 풀었으며, 현재 키의 합이 B보다 크거나 같을 경우 탐색을 그만하면 된다.
탐색을 그만할때, 차이가 작다면 저장한다.
#include<iostream>
#include<vector>
using namespace std;
int out = 0;
int N, B;
void dfs(vector<int> h, int index, int cur)
{
if (cur >= B)
{
if (out > cur - B)
out = cur - B;
return;
}
for (int i = index; i < N; i++)
dfs(h, i + 1, cur + h[i]);
}
int main(int argc, char** argv)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int test_case;
int T;
cin >> T;
for (test_case = 1; test_case <= T; ++test_case)
{
out = 200000;
cin >> N >> B;
vector<int> HEIGHT(N);
for (int i = 0; i < N; i++) cin >> HEIGHT[i];
dfs(HEIGHT, 0, 0);
cout << '#' << test_case << ' ' << out << '\n';
}
return 0;
}