🌠 "캠프 준비" - 16938번 G4

🎃문제설명

⛺️알고리즘 캠프를 열려면 많은 준비가 필요하다. 그 중 가장 중요한 것은 문제이다. 오늘은 백준이를 도와 알고리즘 캠프에 사용할 문제를 고르려고 한다.

백준이는 문제를 N개 가지고 있고, 모든 문제의 난이도를 정수로 수치화했다. i번째 문제의 난이도는 Ai이다.

캠프에 사용할 문제는 두 문제 이상이어야 한다. 문제가 너무 어려우면 학생들이 멘붕에 빠지고, 문제가 너무 쉬우면 학생들이 실망에 빠지게 된다. 따라서, 문제 난이도의 합은 L보다 크거나 같고, R보다 작거나 같아야 한다. 또, 다양한 문제를 경험해보기 위해 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이는 X보다 크거나 같아야 한다.

캠프에 사용할 문제를 고르는 방법의 수를 구해보자.

입력

첫째 줄에 N, L, R, X가 주어진다.

둘째 줄에는 문제의 난이도 A1, A2, ..., AN이 주어진다.

출력

캠프에 사용할 문제를 고르는 방법의 수를 출력한다.

🔒제한사항

• $1 ≤ N ≤ 15$
• $1 ≤ L ≤ R ≤ 10^9$
• $1 ≤ X ≤ 10^6$
• $1 ≤ Ai ≤ 10^6$

💾입출력 예

입력	출력
3 5 6 1 1 2 3	2
4 40 50 10 10 20 30 25	2
5 25 35 10 10 10 20 10 20	6

알고리즘 분류

• 수학
• 브루트포스 알고리즘
• 조합론
• 백트래킹

🌟문제 이해 및 풀이계획

✏️일단, 캠프에 사용할 문제가 몇 문제인지 파악한다. 2문제였다면 이중 for문으로 간단하게 검사할 수 있었을텐데 2문제 이상이었기 때문에 조합을 이용하여 모든 경우를 체크해야 했다.

✏️백트래킹을 이용하여 for문에 2~N개를 뽑는 경우를 모두 검사해주었다.

✍🏻내 코드1 - 정답코드

package BOJ;

import java.util.Scanner;

/*
 * 2021.12.11 daily algo/commit
 * 
 * Brute Force, Combination
 */

public class boj_16938 {
	
	static int answer = 0;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int L = sc.nextInt();
		int R = sc.nextInt();
		int X = sc.nextInt();
		int[] difficulty = new int[N];
		boolean[] visited = new boolean[N];
		
		for(int i=0; i<N; i++) {
			difficulty[i] = sc.nextInt();
		}
		
		// i는 선택한 문제 수
		for(int i=2; i<=N; i++) {
			combination(difficulty, visited, N, i, 0, L, R, X);
		}
		
		System.out.println(answer);
		sc.close();
	}

	public static void combination(int[] difficulty, boolean[] visited, int n, int r, int start, int L, int R, int X) {
		if(r == 0) {
			int sum = 0;
			int max = 0;
			int min = Integer.MAX_VALUE;
			for(int i=0; i<n; i++) {
				if(visited[i]) {
					if(max < difficulty[i]) max = difficulty[i];
					if(min > difficulty[i]) min = difficulty[i];
					sum += difficulty[i];
				}
			}
			if(sum >= L && sum <= R && max - min >= X) answer += 1;
			return;
		}
		
		for(int i=start; i<n; i++) {
			visited[i] = true;
			combination(difficulty, visited, n, r-1, i+1, L, R, X);
			visited[i] = false;
		}
	}
}

강의내용

✔️시간 복잡도 : $2^{15} (N<=15)$ => 32786경우가 최대. 조건에 의해 경우의 수 더 작아진다.

✔️경우의 수가 많지 않으므로 조합을 이용해서 모두 구해본다.

✔️구해야 하는 값

• 문제의 개수
• 난이도의 합
• 가장 어려운 문제의 난이도
• 가장 쉬운 문제의 난이도