[알고리즘] 16938번

오늘 풀어볼 문제는 백준 16938번 문제 "캠프 준비" 이다.

이 문제는 골드5 문제이고 브루트 포스 문제이다.

문제

알고리즘 캠프를 열려면 많은 준비가 필요하다. 그 중 가장 중요한 것은 문제이다. 
오늘은 백준이를 도와 알고리즘 캠프에 사용할 문제를 고르려고 한다.

백준이는 문제를 N개 가지고 있고, 모든 문제의 난이도를 정수로 수치화했다. i번째 문제의 난이도는 Ai이다.

캠프에 사용할 문제는 두 문제 이상이어야 한다. 
문제가 너무 어려우면 학생들이 멘붕에 빠지고, 문제가 너무 쉬우면 학생들이 실망에 빠지게 된다. 
따라서, 문제 난이도의 합은 L보다 크거나 같고, R보다 작거나 같아야 한다. 
또, 다양한 문제를 경험해보기 위해 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이는 X보다 크거나 같아야 한다.

캠프에 사용할 문제를 고르는 방법의 수를 구해보자.

입력

첫째 줄에 N, L, R, X가 주어진다.

둘째 줄에는 문제의 난이도 A1, A2, ..., AN이 주어진다.

출력

캠프에 사용할 문제를 고르는 방법의 수를 출력한다.

📌수 많은 시도📌

package gold5.b16938;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N, L, R, X;
    static int result;
    static int[] array;
    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());

        st = new StringTokenizer(br.readLine());
        array = new int[N];

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

        Arrays.sort(array);
        cal(0, 0, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);

        System.out.println(result);
    }
    private static void cal(int index, int count, int nowNumber, int max, int min) {
        if(count >= 2) {
            if (nowNumber >= L && nowNumber <= R && max - min >= X) {
                result += 1;
            }
        }
        for (int i = index; i < N; i++) {
            cal(i+1,count+1, nowNumber + array[i], Math.max(max, array[i]), Math.min(min, array[i]));
        }
    }
}

음.. 첫 번째 도전만에 성공한 것은 아닌데, 성공 전 실패 코드들을 미리 저장을 안 해놔서 못 올렸다.
왜냐하면 멍청한 실수들을 했다..

일단 첨에는 visited boolean 함수를 통해 최대한 해보려고 했는데, 중복된 값이 계속 result에 저장이 되어서 구글링을 했더니 index를 함수에 넣으라해서 그 방법으로 풀어나갔다.

하지만 계속 result가 2가 나와야 할 땐 3이 나오고 3이 나와야 할 땐 4 계속 예상 결과에서 +1이 되어서 출력이 됐다.
어디서 잘못된건지 한참을 찾다가 결국 못 찾아서 지피티를 돌려보니 바보처럼
cal(i+1,count+1, nowNumber + array[i], Math.max(max, array[i]), Math.min(min, array[i])); 이 부분을
cal(index+1,count+1, nowNumber + array[i], Math.max(max, array[i]), Math.min(min, array[i])); 이렇게 재귀호출을 하고 있었다...

재귀 호출이 아리까리 했는데, 연속으로 문제를 풀어보니깐 방향성을 약간 찾은 것 같다... 하지만 아직까지 온전히 혼자의 힘으로 풀긴 어려운 것 같다 ㅎㅎ

1일 2문제 계속해보자!!🔥

[문제 출처] https://www.acmicpc.net/problem/16938