[풀이]백준 풀이(VIII/16936 등 )

문제풀이

[RE]캠프준비(16938, 구현)

• 2<=N<=15, N=문제의 개수
• L<=난이도의합<=R, 최고난이도 - 최저난이도 >= X
• 최악의 경우의 수 = 2^N = O(2^N)
• 어려운 것: 최고난이도, 최저난이도 (무엇을 선택하는지에 따라 계속 변경됨)

풀이1과 2는 조삼모사

풀이1. 구현 후 필요한 조건만을 나열해서 전체 확인

풀이2. 선택과 동시에 모든 것을 처리함(재귀형태, 인자가 많다)

회고

나는 재귀를 더럽게못짠다…. 심지어 INPUT을 순서를 다르게받아서 계속 헛짓을 했다.

재귀가 아닌형태로 다시 짜서 제출하자

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>

#define MAX 1000000
using namespace std;

int n, l, x, r;
int A[15];
int Answer=0;
bool choice[15];

int go(int index, int cnt, int sum, int easy, int hard){

	if(index==n)
	{
		if(cnt >= 2 && l <= sum && sum <= r && hard-easy >= x )	return 1;
		else return 0;
	}
	//선택O
	int cnt1= go(index+1, cnt+1, sum+A[index], min(easy,A[index]), max(hard,A[index]));
	//선택X
	int cnt2 = go(index+1, cnt, sum, easy, hard);
	return cnt1+cnt2;
}

int main(){
	//N=문제 수,
	//L<= SUM(문제난이도) <=R
	//R-L>=X
	//1<=N   <=15
	//1<=L<=R<=1,000,000,000
	//1<=X   <=1,000,000
	//1<=A[i]<=1,000,000
	cin >> n >> l >> r >> x;
	for(int i=0; i<n; i++){
		cin >> A[i];
	}
	cout << go(0,0,0, MAX, 0);
}