[백준/Java] 16938: 캠프 준비

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

 

 

조건

• TimeLimit = 2s
• 문제수 (1<=N<=15), 문제 난이도 합 (L<=난이도 합<=R, 1<=L<=R<=10억), 가장 어려운 문제와 가장 쉬운 문제차이 (X>=100만), 난이도 (A<=100만)
• 문제를 고를 수 있는 모든 경우의 수를 구하여라

 

풀이

• 완전탐색 -> 백트래킹
  • 문제를 특정 개수만큼 뽑으라는게 아니기 때문에 선택/미선택 방식으로 가자
  • N이 15라면, O(2^15) ~= O(6천만) 이므로 가능 (2^26 이하면 다 가능)
  • 이때 순서가 필요없으므로 조합이다 (visited 필요없음)
  • 선택한 문제는 boolean[]으로 기억해두고, sum할때 사용하자
  • 문제들은 난이도 순서대로 정렬시켜서 가장 쉬운문제와 가장 어려운 문제를 뽑을 수 있게 하자

 

코드

import java.io.*;
import java.util.*;


public class Main {

	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int n;
	static int l;
	static int r;
	static int x;
	static int[] arr;
	static int cnt = 0;
	static boolean[] select;
	
	
	public static void main(String[] args) throws IOException {

		// input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		
		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());
				
		st = new StringTokenizer(br.readLine());
		arr = new int[n];
		for (int i=0; i<n; i++) arr[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(arr);
		
		// dfs
		select = new boolean[n];
		dfs(0);
		
		// result
		System.out.print(cnt);
	}
	
	
	
	
	static void dfs(int size) {
		
		if (size == n) {
			
			boolean first = true;
			int min = 0;
			int max = 0;
			int sum = 0;
			
			for (int i=0; i<n; i++) {
				
				if (select[i]) {
					
					if (first) {
						min = arr[i];
						first = false;
					}
					max = arr[i];
					sum += arr[i];	
				}
			}
			
			if (l<=sum && sum<=r && max-min>=x) cnt++;
			
			return;
		}
		
		// non select
		dfs(size+1); 
		
		// select
		select[size] = true; 
		dfs(size+1);
		select[size] = false;
		
	}
	
}