[G5] 백준 16938번 캠프 준비 C++ 백트래킹, 정렬

리뷰

 

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

문제 N개를 조합하여 난이도의 합이 L~R이며 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이가 X이상인 조합의 개수를 찾는 문제

 

 

전역 변수

• n : 문제의 개수를 저장할 변수
• l, r : 문제 난이도 합의 최소, 최대 값을 저장할 변수
• x : 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이의 최소값을 저장할 변수
• ans : 문제 조합의 개수를 저장할 변수
• lst : 문제의 난이도를 저장할 배열
• c : 선택한 문제의 난이도를 저장할 벡터

 

함수

1. dfs

void dfs(int level, int sum) {
	if (sum > r) return;
	if (level == n) {
		if (sum < l) return;
		if (!c.empty() && *--c.end() - *c.begin() < x) return;
		ans++;
		return;
	}

	c.push_back(lst[level]);
	dfs(level + 1, sum + lst[level]);
	c.pop_back();
	
	dfs(level + 1, sum);
}

 

문제를 선택하는 모든 경우를 탐색하기 위한 함수

 

 

문제풀이

1. n, l, r, x에 값을 입력 받고, n개의 문제의 난이도를 lst배열에 입력 받아준다.
2. sort함수를 통해 lst배열을 오름차순으로 정렬해 준다.
3. dfs함수에 0, 0을 매개변수로 전달하여 호출해 준다.
4. dfs함수는 재귀 단계를 level, 현재 난이도의 합 sum을 매개변수로 전달 받는다.
5. 첫번째 기저 조건으로 sum이 r보다 커졌을 경우 리턴해 준다.
6. 두번째 기저 조건으로 level이 n에 도달했을 경우, sum이 l보다 작을 경우 리턴해 준다, c가 비지 않았고, c의 가장 뒷 요소와 가장 앞의 요소의 차이가 x보다 작을 경우 리턴해 준다.
7. 두번째 기저 조건에서 위 두 조건에 부합하지 않은 경우 ans를 증가시키고 리턴해 준다.
8. 기저 조건에 해당하지 않을 경우 c에 lst[level]을 추가하고, 재귀 단계 증가, sum에 lst[level]를 더해 dfsd함수를 호출한다.
9. 재귀가 종료되면 c에서 요소를 빼내어 주고, dfs함수에 재귀 단계만 증가시켜 한번 더 dfs함수를 호출해 준다.
10. 모든 재귀가 종료된 후 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 가장 어려운 문제와 가장 쉬운 문제를 쉽게 식별하기 위해 lst배열을 오름차순으로 정렬해 주었다.
2. sum이 r보다 커질 경우 정답이 될 수 없으니 가지치기를 진행해 주었다.
3. N값이 15이하이므로 현재 요소를 선택 하거나 선택하지 않은 두가지 선택지로 백트래킹을 진행해 주었다.
4. 결과적으로 최대 2^15의 시간 복잡도로 문제를 해결할 수 있다.

 

정답 코드

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

int n, l, r, x, ans;
int lst[15];
vector<int> c;

void dfs(int level, int sum) {
	if (sum > r) return;
	if (level == n) {
		if (sum < l) return;
		if (!c.empty() && *--c.end() - *c.begin() < x) return;
		ans++;
		return;
	}

	c.push_back(lst[level]);
	dfs(level + 1, sum + lst[level]);
	c.pop_back();
	
	dfs(level + 1, sum);
}

int main() {
	cin >> n >> l >> r >> x;
	for (int i = 0; i < n; ++i) cin >> lst[i];
	sort(lst, lst + n);
	dfs(0, 0);
	cout << ans;
}