16938 캠프 준비

캠프 준비

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

570

381

306

67.699%

문제

알고리즘 캠프를 열려면 많은 준비가 필요하다. 그 중 가장 중요한 것은 문제이다. 오늘은 백준이를 도와 알고리즘 캠프에 사용할 문제를 고르려고 한다.

백준이는 문제를 N개 가지고 있고, 모든 문제의 난이도를 정수로 수치화했다. i번째 문제의 난이도는 Ai이다.

캠프에 사용할 문제는 두 문제 이상이어야 한다. 문제가 너무 어려우면 학생들이 멘붕에 빠지고, 문제가 너무 쉬우면 학생들이 실망에 빠지게 된다. 따라서, 문제 난이도의 합은 L보다 크거나 같고, R보다 작거나 같아야 한다. 또, 다양한 문제를 경험해보기 위해 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이는 X보다 크거나 같아야 한다.

캠프에 사용할 문제를 고르는 방법의 수를 구해보자.

입력

첫째 줄에 N, L, R, X가 주어진다.

둘째 줄에는 문제의 난이도 A1, A2, ..., AN이 주어진다.

출력

캠프에 사용할 문제를 고르는 방법의 수를 출력한다.

제한

• 1 ≤ N ≤ 15
• 1 ≤ L ≤ R ≤ 109
• 1 ≤ X ≤ 106
• 1 ≤ Ai ≤ 106

(풀이)

1.  문제 수 N개를 선택 여부에 대한 2^N방법 - 1개선택(N) => 2^N - N

 

2.  O(2^N) 시간복잡도를 갖는다.  N의 최대범위는 15 이므로 2^15이다 => 32,768.

 

3.  재귀로 모두 선택해보며 2개이상 일때 주어진 조건들을 적용하여 검사한다.

   ★ 주의 사항은 2개이상일때 조건이 참이면 ans+=1을하고 return을 하면안된다.

   ★ 이유는 2개이상인 문제가 3개 4개가 될때도 있으니 return하지말고 끝까지 해봐야 한다.

 

4. 속도를 높이기 위해 sum이 R을 초과하는순간 호출스택을 종료시킨다.

 

#include<iostream>
#include<vector>
using namespace std;

void go(int index, int cnt, int min, int max, int sum);
int N, L, R, X;

int check[15];
vector<int> v;
int ans;
int main(void)
{
	cin >> N >> L >> R >> X;
	int n = 0;
	for (int i = 0; i < N; ++i)
	{
		cin >> n;
		v.push_back(n);
	}
	go(0, 0, 1e9, 0, 0);
	cout << ans << '\n';
	return 0;
}
void go(int index, int cnt, int min, int max, int sum)
{
	if (index > N || sum > R)
		return;

	if (cnt >= 2 && max - min >= X && sum >= L && sum <= R)
	{
		ans += 1;
	}

	for (int i = index; i < N; ++i)
	{
		if (check[i] == false)
		{
			check[i] = true;

			if (cnt >= 1)
			{
				min = 1e9;
				max = 0;
				for (int k = 0; k < N; ++k)
				{
					if (check[k])
					{
						if (min > v[k])
							min = v[k];

						if (max < v[k])
							max = v[k];
					}
				}
			}
			go(i + 1, cnt + 1, min, max, sum + v[i]);
			check[i] = false;
		}
	}

}