swea 1486. 장훈이의 높은 선반

[문제]

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&categoryId=AV2b7Yf6ABcBBASw&categoryType=CODE

SW Expert Academy

[풀이]

dfs로 조합을 구하는 방법으로 풀었다.

합이 현재까지 구해둔 최소값보다 커지면 재귀를 하지 않고 넘어가는 식으로 시간을 줄였다.

 

#include <iostream>
#include <algorithm>//min
using namespace std;

int T, N, B;
int H[21];
bool check[21];
int Min;

void dfs(int h, int b) {
	if (b >= B) {
		Min = min(Min, b);
		return;
	}
	for (int i = h; i < N; i++) {
		if (check[i] || b+H[i] >= Min)
			continue;
		check[i] = true;
		dfs(i, b + H[i]);
		check[i] = false;
	}
}

void solution() {
	cin >> T;
	for (int t = 1; t <= T; t++) {
		cin >> N >> B;
		Min = 987654321;
		for (int i = 0; i < N; i++) {
			cin >> H[i];
		}
		dfs(0, 0);
		cout << '#' << t << ' ' << Min - B << '\n';
	}
}

int main() {
	solution();
	return 0;
}