🌠 "营业的准备"-16938号G 4

🎃問題の説明
アルゴリズムキャンプを開催するには多くの準備が必要だ.その中で最も重要なのは問題です.今日は白俊選アルゴリズムキャンプで使う問題を手伝います.
白俊にはN個の問題があり、すべての問題の難易度を整数にした.i最初の問題の難易度はAiです.
キャンプ場の使用の問題は2つ以上の問題でなければならない.問題が難しすぎると、学生は崩壊し、問題が簡単すぎると、学生は失望します.したがって、問題の難易度の和はL以上、R以下でなければならない.また、さまざまな問題を体験するためには、最も難しい問題と最も容易な問題の難易度の違いはX以上でなければならない.
キャンプ場で使用する問題を選ぶ方法を見つけましょう.
入力
1行目はN,L,R,Xである.
2行目は問題難易度A 1、A 2、...ANが与えられた.
しゅつりょく
キャンプで使用する問題を選択する方法の数を出力します.
🔒せいげんじょうけん

1≤N≤151 ≤ N ≤ 151≤N≤15

1≤L≤R≤1091 ≤ L ≤ R ≤ 10^91≤L≤R≤109

1≤X≤1061 ≤ X ≤ 10^61≤X≤106

1≤Ai≤1061 ≤ Ai ≤ 10^61≤Ai≤106

💾I/O例
入出力35 6 11 2 324 40 50 1010 20 25 35 1010 206
アルゴリズム分類

数学

ルーティング転送アルゴリズム

組合せ論

バックグラウンドトラッキング

🌟計画問題の理解と解答
▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼2問であれば2問for문で簡単にチェックできますが、2問以上なので組み合わせで全てチェックします.
▼▼back trackingチェック24142で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;
		}
	}
}

レッスン内容
✔時間複雑度:最大値は215(N<=15)2^{15}(N<=15)=>です.条件によって、状況の数はもっと小さくなります.
ААААААААААААААА\104
✔¥

題

難易度の和

最も難しい問題難易度

最も簡単な問題難易度