[BOJ] 16938. 캠프 준비

[작성일]

• 2022-02-23

[분류]

• dfs
• 백트래킹
  
  
  

[문제링크]

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

[요구사항]

• 조건에 맞게 문제를 선택하는 경우의 수를 모두 구하라.
  
  
  

[풀이]

조합으로 문제를 2개이상 뽑고 이후 조건에 맞는지 검사해주고 난 뒤, 맞으면 answer++해주면 되는 전형적인 백트래킹 문제이다. 가장 높은 점수와 낮은 점수를 구별하기 위해 처음에 배열을 정렬해주고 진행하였다.

[코드]

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

public class Main {
    static int N, L, R, X;
    static int[] problem;
    static int answer = 0;

    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());
        }
        Arrays.sort(problem);

        for (int i = 0; i < N - 1; i++) {
            getProblems(i, 1, problem[i], problem[i], problem[i]);
        }
        System.out.println(answer);
    }

    public static void getProblems(int idx, int cnt, int sum, int easy, int hard) {
        if (cnt >= 2) {
            if (L <= sum && sum <= R && hard - easy >= X) {
                answer++;
            }
        }
        for (int i = idx + 1; i < problem.length; i++) {
            getProblems(i, cnt + 1, sum + problem[i], easy, problem[i]);
        }
    }
}