[알고리즘] 백준 - 캠프 준비

백준 - 캠프 준비

통과 못한 내 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;


public class Main {

    static int N, L, R, X;
    static int[] arr;
    static int ans;
    static Set<String> ansSet = new HashSet<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        L = Integer.parseInt(inputs[1]);
        R = Integer.parseInt(inputs[2]);
        X = Integer.parseInt(inputs[3]);
        arr = new int[N];
        inputs = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(inputs[i]);
        }

        solve(0, 0, 0, Integer.MAX_VALUE, Integer.MIN_VALUE, "");
        System.out.println(ansSet.size());
    }

    private static void solve(int curPos, int curSum, int curCount, int minValue, int maxValue, String choice) {
        if (curCount >= 2) {
            if (L <= curSum && curSum <= R && Math.abs(maxValue - minValue) >= X) {
                ans++;
                ansSet.add(choice);
            }
        }

        if (curPos >= N) {
            return;
        }

        solve(curPos + 1, curSum + arr[curPos], curCount + 1, Math.min(minValue, arr[curPos]), Math.max(maxValue, arr[curPos]), choice + " " +Integer.toString(arr[curPos]));
        solve(curPos+1, curSum, curCount, minValue, maxValue, choice);
    }
}

처음에는 조건을 확인하는 부분에 습관처럼 return을 넣어서 탈출하게 했다. 하지만 1번과 2번 문제를 선택하는 방법에 이어 1, 2, 3을 선택하는 방법도 있을 수 있다. 따라서 여기서 return을 하지 말아야한다.

통과 못한 내 풀이. 왜 통과 못할까? 결국 문제가 N개 있다고하면 문제를 선택하는 모든 경우의 수는 2^N개 아닌가?

통과 한 내 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;


public class baekjoon_16938 {
    static int N, L, R, X;
    static int[] arr;
    static int ans;
    static Set<String> ansSet = new HashSet<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        L = Integer.parseInt(inputs[1]);
        R = Integer.parseInt(inputs[2]);
        X = Integer.parseInt(inputs[3]);
        arr = new int[N];
        inputs = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(inputs[i]);
        }

        solve(0, 0, 0, Integer.MAX_VALUE, Integer.MIN_VALUE, "");
        System.out.println(ansSet.size());
    }

    private static void solve(int curPos, int curSum, int curCount, int minValue, int maxValue, String choice) {
        if (curCount >= 2) {
            if (L <= curSum && curSum <= R && Math.abs(maxValue - minValue) >= X) {
                ans++;
                ansSet.add(choice);
            }
        }

        if (curPos >= N) {
            return;
        }

        solve(curPos + 1, curSum + arr[curPos], curCount + 1, Math.min(minValue, arr[curPos]), Math.max(maxValue, arr[curPos]), choice + " " +Integer.toString(curPos));
        solve(curPos+1, curSum, curCount, minValue, maxValue, choice);
    }
}

2진법처럼 푸는 방식 자체는 맞았다. 하지만 예전 실패한 풀이를 보면 지나온 경로를 arr[curPos] 즉 문제의 번호가 아니라 문제의 난이도를 더해주고 있었다. 그래서 같은 난이도의 문제들이 있으면 에러가 발생할 수 있다.