[백준] 16938 캠프 준비 - Brute Force / Java

• 문제 링크

16938번: 캠프 준비

 

• 풀이 과정

문제의 개수 n, 조건값 l, x, r 과 각 문제의 난이도를 입력받아 크기가 n인 배열 arr 에 저장 및 오름차순 정렬한다.

 

재귀 호출 함수에 문제 난이도 값의 합 sum, 선택된 난이도의 최솟값 min, 최댓값 max 와

함수 내부의 반복문의 시작값 idx, 재귀 함수의 깊이 depth 값을 매개 변수로 전달하여 실행한다.

 

배열에 저장된 값을 sum 변수에 더한 값, 해당 값을 최소값,  최대값과 비교해 갱신한 값,

중복된 문제를 선택하지 않기 위해 i + 1 과 문제 하나가 추가로 선택됐음을 나타내는 depth + 1 을

매개 변수로 전달해 재귀 호출한다.

 

depth >= 2 일 시 최소 두 문제 이상을 사용해야 하는 조건에 만족하므로 

전달된 sum 값이 l 이상, r 이하이며 최소값과 최댓값의 차이가 x를 만족할 시,

방법의 수를 나타내는 cnt 변수에 cnt++ 를 수행하며 최종적으로 해당값을 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int n, l, r, x, cnt;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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());
        arr = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(arr);

        recur(0, Integer.MAX_VALUE, 0, 0, 0);

        bw.write(cnt + "\n");
        bw.flush();
    }

    private static void recur(int sum, int min, int max, int idx, int depth) {
        if (depth >= 2) {
            if (sum >= l && sum <= r && max - min >= x)
                cnt++;
        }

        for (int i = idx; i < n; i++)
            recur(sum + arr[i], Math.min(min, arr[i]), Math.max(max, arr[i]), i + 1, depth + 1);
    }

}