[BOJ] 16938. 캠프 준비 - Java

📝 문제

문제 | 백준 16938. 캠프 준비

💡 풀이 과정

⛓ 사용한 알고리즘: 비트마스킹

완전 탐색으로 풀어야 하는 문제이다. 고를 수 있는 문제 개수의 제한이 없고, 문제의 난이도에 대한 제한(일정한 차이가 존재한다거나 겹치지 않는다거나 등등…)도 없기 때문에 모든 경우의 수를 탐색해보며 정답을 도출해야 하기 때문이다. 다행이 N의 최댓값이 15이기 때문에 무리없이 완전 탐색을 해볼 수 있다.

백트래킹을 이용해서도 풀 수 있지만, 이번에는 비트마스킹을 이용해 완전 탐색을 해 보았다. N개의 비트를 모두 0으로 채우는 것과 모두 1로 채우는 경우 사이의 모든 비트를 선택/비선택 해보면서 모든 경우의 수를 파악하는 것이다. 예를 들어 N=3일 때에는 000 ~ 111 범위를 탐색할 수 있고, 이 때 각 비트는 문제 난이도 배열의 인덱스가 된다. 따라서 011 의 경우는 2번 문제와 3번 문제를 선택한 경우를 의미한다.

위의 방식으로 문제를 선택하고, 문제 선택을 완료했다면 주어진 조건에 맞는지 확인한다. 확인해야 할 조건은 다음과 같다.

• 문제가 2가지 이상일 것
• 문제의 난이도 합이 L이상이고 R이하일 것
• 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이는 X이상일 것

모든 조건을 통과했다면 해당 문제의 조합은 가능한 경우이므로 정답 개수를 카운팅해주면 된다.

추가로 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이를 빠르게 구하기 위해선 배열을 오름차순으로 정렬한 후, 선택한 문제 중 가장 앞쪽에 있는 문제와 가장 뒤쪽에 있는 문제의 인덱스를 저장해두면 된다. 다만 이 문제에서는 N이 크지 않아 별도로 코드를 작성하진 않았다(기대되는 효율에 비해 코드만 번잡스러워지는 느낌).

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static int N,L,R,X,ans;
	
	static int[] arr;
	
	static void pick() {
		
		int cnt,l,r,sum;
		
		for(int i=1;i<(1<<N);i++) {
			cnt=0;
			l=Integer.MAX_VALUE;
			r=Integer.MIN_VALUE;
			sum=0;
			
			for(int j=0;j<N;j++) {
				if((i&(1<<j))>0) {
					cnt++;
					l = Math.min(l, arr[j]);
					r = Math.max(r, arr[j]);
					sum += arr[j];
				}
			}
			
			if(cnt<2 || sum<L || sum>R || r-l<X) continue;
			
			ans++;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		} //end input
		
		Arrays.sort(arr);
		
		ans=0;
		pick();
		
		System.out.println(ans);
	}
}