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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw

SW Expert Academy

 

간단한 dfs 문제

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int N, B;
vector<int> height;
vector<int> visited;
int S = 1e9;
void init();

void dfs(int now, int sum) {
	if (sum > S) return;

	if (sum >= B) {
		S = min(S, sum);
		return;
	}

	for (int i = now; i < N; i++) {
		if (visited[i]) continue;
		visited[i] = 1;
		sum += height[i];
		dfs(i, sum);
		sum -= height[i];
		visited[i] = 0;
	}
}

int main() {
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		init();
		cin >> N >> B;
		for (int i = 0; i < N; i++) {
			int h;
			cin >> h;
			height.push_back(h);
		}

		visited.assign(N, 0);
		dfs(0, 0);

		cout << "#" << tc << " " << S - B << endl;
	}

	return 0;
}

void init() {
	height.clear();
	S = 1e9;
}