[SWEA] (C++) D4 1486. 장훈이의 높은 선반

크게 어렵지않은 완전탐색 문제이다.

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;
}