[알고리즘] Java / 백준 / 캠프 준비 / 16938

[알고리즘] Java / 백준 / 캠프 준비 / 16938

문제

문제 링크

접근 방식

1. i = 2 ~ N일 때 N개 중 i개의 문제를 조합으로 선택한다.
2. 조건 : 선택한 i개의 문제의 난이도 합이 L 이상 R 이하일 경우
3. 조건 : 선택한 i개의 문제 중 쉬운 문제와 어려운 문제의 난이도 차이가 X 이상일 경우
4. 2번과 3번을 모두 만족할 경우, 경우의 수(answer)를 1 올린다.

코드

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

public class Main_16938 {

	static int[] numList;
	static int answer;
	static int N,L,R,X;
	static int[] A;
	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());
		
		st = new StringTokenizer(br.readLine());
		A = new int[N];
		for(int i=0;i<N;i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		answer = 0;
		

		for(int i=2;i<=N;i++) {
			numList = new int[i];
			combi(0,0,i);
			
		}
		
		System.out.println(answer);
		
	}
	
	public static void combi(int start, int cnt, int target) {
		if(cnt == target) {
			if(isSumBetweenLR() && isDiffBiggerThanX()) answer++;
			
			return;
		}
		
		for(int i=start;i<N;i++) {
			numList[cnt] = i;
			combi(i+1,cnt+1,target);
		}
	}
	
	public static boolean isSumBetweenLR() {
		int sum = 0;
		for(int i=0;i<numList.length;i++) {
			sum+=A[numList[i]];
		}
		
		if(sum >= L && sum <= R) return true;
		return false;
	}
	
	public static boolean isDiffBiggerThanX() {
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		
		for(int i=0;i<numList.length;i++) {
			if(min > A[numList[i]]) min = A[numList[i]];
			if(max < A[numList[i]]) max = A[numList[i]];
		}
		
		if(max - min >=X) return true;
		return false;
	}

}