취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6148번 문제인 Bookshelf 2이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/6148 

쌓인 소의 높이는 소의 순서에 관계없이 어떤 소가 쌓여있는지에만 영향을 받는다. 이러한 소의 조합(소 0마리로 이루어진 조합도 포함한다)은 각 소가 조합에 포함되어있는지의 여부로 결정되므로 총 $2^N$가지 존재한다.

가능한 모든 방법으로 소를 쌓았을 때의 높이를 하나하나 조사해 문제를 해결하자. $2^{20}=1048576$이므로 이와 같은 방법으로 문제를 충분히 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, K;
int ans = 1000000007;
int val, A[20];

void func(int idx) {
	if (idx == N) {
		if (val < K) return;
		ans = min(ans, val - K);
		return;
	}
	func(idx + 1);
	val += A[idx];
	func(idx + 1);
	val -= A[idx];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> A[i];
	func(0);

	cout << ans;
}