[BOJ] 캠프 준비

[16938] 캠프 준비

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

• 캠프에 사용할 문제를 고르는 방법의 수를 구하는 문제
• N : 가지고 있는 문제 수
• L : 문제 난이도 하한
• R : 문제 난이도 상한
• X : 가장 쉬운 문제와 가장 어려운 문제 난이도 차이
• 1. 문제는 두 문제 이상
• 2. 뽑은 문제의 난이도는 L 이상 R 이하
• 3. 가장 쉬운 문제와 가장 어려운 문제의 난이도 차이는 X와 같거나 커야한다.

 

 

Solution

• permutation 활용 문제
• 문제는 두 문제 이상이어야 하기 때문에 2 ~ N까지 size를 바꿔가면서 permutation() 함수를 돌렸다.
• 뽑은 문제를 temp 리스트에 담아 문제의 조건에 부합하면 count++를 해주었다.

 

 

소스코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	static int n, l, r, x, count;
	static int[] a;
	static List<Integer> p, temp;
	static boolean[] c;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringTokenizer st = new StringTokenizer(sc.nextLine());
		n = stoi(st.nextToken());
		l = stoi(st.nextToken());
		r = stoi(st.nextToken());
		x = stoi(st.nextToken());
		init();

		st = new StringTokenizer(sc.nextLine());
		for (int i = 0; i < n; i++) {
			p.add(stoi(st.nextToken()));
		}
		count = 0;
		for (int i = 2; i <= p.size(); i++) {
			permutation(0, 1, i);
		}
		System.out.println(count);
	}

	public static void permutation(int depth, int start, int size) {
		if (depth == size) {
			temp = new ArrayList<>();
			solve();
			return;
		}

		for (int i = start; i <= n; i++) {
			a[depth] = i;
			permutation(depth + 1, i + 1, size);
		}
	}

	public static void solve() {
		for (int i : a) {
			if (i == 0)
				continue;
			temp.add(p.get(i-1));
		}
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		int sum = 0;
		for(int i: temp) {
			sum += i;
			min = Math.min(min, i);
			max = Math.max(max, i);
		}
		if(sum < l || sum > r)
			return;
		if(max - min < x)
			return;
		
		count++;
	}

	public static void init() {
		a = new int[n];
		p = new ArrayList<>();
	}

	public static void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}