[백준] 16938 캠프 준비 - Java

 

 

 

문제 출저

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

16938번: 캠프 준비

 

 

 

문제 풀이 

난이도가 있는 문제 n개가 주어집니다. 

2개 이상의 문제를 선택해야 합니다.

그 중, 문제난이도의 합이 L 이상, R 이하, 선택 된 문제 중 최대 난이도 - 최소 난이도가 X 이상인 경우의 수를 구해야 합니다.

 

DFS를 이용해 경우의 수를 구하는 걸로 문제 풀었습니다. 

탐색할 때 문제의 합이 R보다 크면 탐색을 중단했습니다. 

문제를 풀 때 최소값을 구할 때 초기값을 잘 못 설정하여 0%에서 계속 틀렸습니다.

최소값의 초기값을 Integer.MAX_VALUE로 두어 문제를 해결했습니다.

 

 

 

소스 코드

package baekjoon.backjoon10.day2131.day25;

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

/*
캠프 준비
https://www.acmicpc.net/problem/16938
 */

public class B16938 {


    static int n, l, r, x;
    static int[] problem;
    static int answer;
    static boolean[] selected;


    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()); // 문제 나이도 차이

        problem = new int[n];

        st = new StringTokenizer(br.readLine());

        for(int i = 0; i < n; i++) {
            problem[i] = Integer.parseInt(st.nextToken());
        }

        answer = 0;

        selected = new boolean[n];
        dfs(0, 0);

        System.out.println(answer);

    }

    public static void dfs(int stage, int number) {

        if(stage >= 2) {
            int minValue = Integer.MAX_VALUE;
            int maxValue = 0;
            int sumValue = 0;

            for(int i = 0; i < n; i++) {
                if(selected[i]) {
                    minValue = Math.min(problem[i], minValue);
                    maxValue = Math.max(problem[i], maxValue);
                    sumValue += problem[i];
                }
            }

            if(sumValue > r) {
                return;
            }

            if(sumValue >= l && sumValue <= r && maxValue - minValue >= x) {
                answer += 1;
            }

        }

        for(int i = number; i < n; i++) {
            if(selected[i] == false) {
                selected[i] = true;
                dfs(stage+1, i+1);
                selected[i] = false;
            }
        }

    }




}