1486. 장훈이의 높은 선반

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

SW Expert Academy

 

 

DFS로 직원 추가해 가면서 높이 합 계산, 최소 값 갱신

#include<iostream>
#include<vector>

using namespace std;

int N, B;
int arr[20];
int mina;

vector<int> vec;


int sum()
{
	int size = vec.size();
	int sum = 0;
	for (int i = 0; i < size; i++)
	{
		sum += vec[i];
	}

	return sum;
}

void DFS(int idx, int cur)
{
	int n = sum();
	if (n >= B)
	{
		if (mina > n - B)
		{
			mina = n - B;
		}
		return;
	}

	for (int i = idx + 1; i < N; i++)
	{
		vec.push_back(arr[i]);
		DFS(i, cur + 1);
		vec.pop_back();
	}

}

int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N >> B;
		mina = 987654321;
		vec.clear();
		for (int i = 0; i < N; i++)
		{
			cin >> arr[i];
		}
			
		for (int i = 0; i < N; i++)
		{
			vec.push_back(arr[i]);
			DFS(i,1);
			vec.pop_back();
		}

		cout << "#" << test_case << " " << mina << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}