[백준] 16938 캠프 준비(C++)

백준 16938 캠프 준비

1. 문제

문제링크

2. 접근법

[ 문제 접근 ]

 

1. 문제를 고르는 경우에 대한 조합을 DFS를 돌려서 구했다.

2. 여러 경우를 생각하기 위해 DFS매개변수를 문제인덱스, 고른 문제의 수, 고른 문제의 합, 고른 문제에서 가장 쉬운 문제와 어려운 문제로 두었다.

3. i번째 문제를 고르는 경우와 고르지 않는 경우를 DFS를 돌리면서 ans에 더해주었다.

 

3. 코드

#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
#define MAX -987654321
#define MIN 987654321
int arr[15];
int n, l, r, x;
//문제 인덱스, 고른 문제수, 고른 문제의 합, 고른문제에서 가장 쉬운문제, 어려운 문제
int DFS(int i, int cnt, int sum, int easy, int hard)
{
	int ans = 0;
	//모든 문제를 다 고르면
	if (i == n)
	{
		if (cnt < 2)
			return 0;
		if (sum < l || sum > r)
			return 0;
		if (hard - easy < x)
			return 0;
		//이 외의 경우 문제를 고름 
		return 1;
	}

	//i번째 문제를 고르지 않는 경우
	ans += DFS(i + 1, cnt, sum, easy, hard);
	//i번째 문제를 고르는 경우
	ans += DFS(i + 1, cnt + 1, sum + arr[i], min(easy, arr[i]), max(hard, arr[i]));

	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//ifstream cin;
	//cin.open("input.txt");

	cin >> n >> l >> r >> x;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	cout << DFS(0, 0, 0, MIN, MAX) << "\n";
	return 0;
}

4. 시간복잡도

N의 최대가 15이므로 문제를 고르는 경우, 고르지 않는 경우를 모두 고려해본다고 가정하면,

15 + 2^15 < 2*10^8 로 2초내에 풀 수 있다.

5. 결과