백준) 16938번: 캠프 준비 in C

 

Made with Stable Diffusion

Problem

16938번: 캠프 준비

 

Solution.

정렬 알고리즘과 백트레킹 중 DFS 를 통해 풀이했다.

 

먼저 오름차순으로 문제의 난이도를 정렬해놓고 풀면 훨씬 좋을 것 같다는 판단 하에 버블 정렬을 이용했다.

그리고 이 문제는 조합으로 풀 수 있을 것 같아 DFS 알고리즘을 사용했다.

DFS 를 하면서 다음과 같은 세 가지 조건이 만족하는 경우 count 를 1씩 늘려가며 답을 구했다.

1) 조합으로 만들어진 원소들의 합이 L보다 크거나 같다. (total >= L)

2) 조합으로 만들어진 원소들의 합이 R보다 작거나 같다. (total <= R)

3) 조합의 가장 작은 원소 값과 가장 큰 원소 값의 차이가 X보다 크거나 같다. (A[cur] - A[first] >= X)

이때 3번 조건은 이미 오름차순으로 정렬된 수열을 가지고 서칭을 하는 것이므로 DFS 시작할 때의 원소 값이 가장 작은 값이 될 것이고, DFS에서 가장 최근에 탐색한 원소 값이 가장 큰 값이 될 것이다. (first, cur).

 

Code.

#include <stdio.h>

int N, A[15], first, L, R, X, count;

void sort(int *arr, int n){
	int temp, i, j;
	
	for(i=0;i<n-1;i++){
		for(j=0;j<n-1;j++){
			if(arr[j] > arr[j+1]){
				temp = arr[j+1];
				arr[j+1] = arr[j];
				arr[j] = temp;
			}	
		}
	}
};

void dfs(int cur, int total){
	int i, X_temp;
	
	X_temp = A[cur] - A[first];
	
	if((X_temp >= X) && (total >= L) && (total <= R))
		count++;
	
	for(i=cur+1;i<N;i++){
		dfs(i, total+A[i]);
	}
};

int main(){
	int i;
	count = 0;
	
	scanf("%d %d %d %d", &N, &L, &R, &X);
	
	for(i=0;i<N;i++)
		scanf("%d", &A[i]);

	sort(A, N);
	
	for(i=0;i<N;i++){
		first = i;
		dfs(i, A[i]);
	}
	
	printf("%d\n", count);
	
	return 0;
}