BOJ_16938_캠프 준비

1

구분: 수학, 부르트포스 알고리즘, 조합론, 백트레킹

언어: Java

• 전략:
  문제를 선택한다 - 개수는 2개 이상 -> 부분 집합을 이용해 문제를 선택하거나 선택하지 않는다
• 문제들의 난이도들의 합을 구한다 -> 선택된 것들을 더한다
• 문제들의 최상 난이도 - 최하 난이도 차를 구한다  -> 배열의 정렬을 이용하여 최대, 최소값을 구한다
• 조건에 맞다면 개수를 1 증가

 

---

2. 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int n, l, r, x, ans;
	static int[] level;
	static boolean[] subset;
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		n = scanner.nextInt();//전체 문제 개수
		l = scanner.nextInt();//합, 최소
		r = scanner.nextInt();//합, 최대
		x = scanner.nextInt();//차, 최소
		
		level = new int[n];//문제 난이도
		subset = new boolean[n];
	
		ans = 0;
		for(int i = 0; i<n; i++) {
			level[i] = scanner.nextInt();
		}
		
		powerSet(0);
		System.out.println(ans);
		
	}//main
	
	//부분 집합을 이용하여 문제를 선택
	private static void powerSet(int cnt) {
		if(cnt >= n) {
			
			//선택된 문제의 수
			int trueCnt = 0;
			for(boolean b : subset) {
				if(b) trueCnt++;
			}
			//2문제 이하면 안써
			if(trueCnt<2)return;
			
			int[] question = new int[trueCnt];
			int idx = 0;
			int sum = 0;//문제 난이도들의 합
			//문제들의 난이도를 더하고, 정렬할 배열
			for(int i = 0; i<n; i++) {
				if(subset[i]) {
					question[idx++] = level[i];
					sum+=level[i];
				}
					
			}
			//정렬하여 최소난이도, 최대 난이도를 구함
			Arrays.sort(question);	
			
			//최상 난이도 - 최하 난이도
			int sub = question[trueCnt-1] - question[0];
			
			//조건에 맞으면 방법 수 증가
			if(sum>=l && sum<=r && sub>=x) {
				ans++;
			}
			
			return;
		}
		
		
		//부분 집합을 생성
		subset[cnt] = true;
		powerSet(cnt+1);
		
		subset[cnt] = false;
		powerSet(cnt+1);
		
		
	}
	
	
}

---

3

• 문제의 수가 2개 이상인데 2개로 보고 조합을 구했었다.
• 난이도의 차가 x보다 크거나 같아야 하는데, 작거나 같다고 하였다 
• 결론: 문제를 꼼꼼하게 읽자