[백준] code.plus(브루트 포스 Part 1,JAVA)16938번, 캠프 준비

문제 링크

16938번: 캠프 준비

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심은

 

1. 2문제 이상 선택해야합니다.

2. 선택한 문제 난이도의 합은 L보다 크거나 같고, R보다 작거나 같아야 합니다.

3. 선택한 문제 난이도의 최대값과 최소값의 차가 X보다 크거나 같아야 합니다.

4. 문제를 선택할 수 있는 경우의 수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 문제를 선택하는 모든 경우의 수를 탐색하여 캠프에서 사용이 가능한지 확인합니다.

 

3. 모든 경우를 탐색 이후 캠프에서 사용 가능한 경우의 개수를 결과로 출력합니다.

 

예제입력 1.

 

1. 입력되는 정보들을 저장합니다.

 

N = 3

L = 5

R = 6

X = 1

문제1 : 1

문제2 : 2

문제3 : 3

 

2. 문제를 선택하는 모든 경우의 수를 탐색하여 캠프에서 사용이 가능한지 확인합니다.

 

문제1 - 문제2 : 1 + 2 = 3(최소 : 1, 최대 : 2, 차이 : 1)

난이도 합(3) < L(5) : X

 

문제1 - 문제3 : 1 + 3 = 4(최소 : 1, 최대 : 3, 차이 : 2)

난이도 합(4) < L(5) : X

 

문제2 - 문제3 : 2 + 3 = 5(최소 : 2, 최대 : 3, 차이 : 1)

L(5) ≤ 난이도 합(5) < R(6), 차이(1) ≥ X(1) : O

 

문제1 - 문제2 - 문제3 : 1 + 2 + 3 = 6(최소 : 1, 최대 : 3, 차이 : 2)

L(5) < 난이도 합(6) ≤ R(6), 차이(2) ≥ X(1) : O

 

3. 모든 경우를 탐색 이후 캠프에서 사용 가능한 경우의 개수를 결과로 출력합니다.

 

가능한 경우의 개수 : 2개를 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해서 입력된 값을 띄어쓰기 기준 나누었습니다.
• 값을 입력받을 때 난이도가 R보다 크면 사용할 수 없기 때문에 넘깁니다.
• cal을 실행하여 문제를 선택하는 모든 경우를 구하는 탐색합니다.
• 탐색하여 조건에 맞는 경우의 개수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 문제를 선택하는 모든 경우를 탐색하여 조건에 맞는지 확인합니다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    static int N,L,R,X, answer = 0;
    static ArrayList<Integer> dif = new ArrayList<>();	//문제 난이도 저장 리스트
    static boolean[] check;	//방문 확인 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        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());
        st = new StringTokenizer(br.readLine(), " ");
        //입력값 저장
        for(int i=0;i<N;i++){
            int A = Integer.parseInt(st.nextToken());
            if(A <= R)	//난이도가 R보다 크면 사용할 수 없습니다.
                dif.add(A);
        }
        check = new boolean[dif.size()];
        //모든 경우 탐색
        for(int i=0;i<dif.size();i++){
            check[i] = true;
            cal(i, 1, dif.get(i), dif.get(i), dif.get(i));
        }

        bw.write(answer + "");	//경우의 수 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //문제를 선택하는 모든 경우 탐색
    static void cal(int index, int count, int value, int max, int min){
        //2개 이상 문제를 선택한 경우
        if(count>1){
            //조건에 만족하는 경우
            if(value <= R && value>=L && max-min >=X)
                answer++;
        }
        //현재 경우에서 다른 문제 선택하기
        for(int i=index+1;i<dif.size();i++){
            if(value + dif.get(i) > R || check[i])
                continue;
            check[i] = true;
            //최대, 최소 난이도 구하기
            int tempMax = Math.max(max, dif.get(i));
            int tempMin = Math.min(min, dif.get(i));
            cal(i, count+1, value + dif.get(i),tempMax, tempMin);
            check[i] = false;
        }
    }
}