[백준 - 16938번] 캠프 준비 - Java //Wello Horld//

이번에는 BOJ의 16938번 문제 "캠프 준비"를 풀어보도록 하자

오랜만에 이런 문제를 풀려고 하니, 뇌에 쥐가 나서 살짝 지끈했다. 처음에 문제를 풀때에는 아래에 첨부한 것과 같이 list를 이용해서, 간편하게 max값과 min값 크기를 구할 수 있도록 했는데, 시간초과가 떠버렸다.

import java.io.*;
import java.util.*;

public class sample {
    static int N, X;
    static long L, R;
    static long[] A;
    static int ans = 0;
    static ArrayList<Integer> list = new ArrayList<Integer>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Long.parseLong(st.nextToken());
        R = Long.parseLong(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        A = new long[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(A);
        calc(0, 0);
        bw.write(ans + "\n");
        bw.flush();
        br.close();
        bw.close();
    }

    public static void calc(long allScore, int i) {
        if (allScore >= L && allScore <= R) {
            if (list.size() >= 2) {
                if (list.get(list.size() - 1) - list.get(0) >= X) {
                    ans++;
                }
            }
        }
        for (int j = i; j < N; j++) {
            if(allScore + A[j] <= R){
                allScore += A[j];
                list.add((int) A[j]);
                calc(allScore, i + 1);
                allScore -= A[j];
                list.remove(list.size() - 1);
            }
        }
    }
}

ArrayList를 이용해서 손쉽게 처음과 마지막 수를 구해줄 수도 있고, 전체크기도 알 수 있지만, 그만큼 시간이 걸린다는 뜻이므로, list가 아닌 루프가 돌아가면서 현재 체크한 수들의 크기, max, min 을 구해주게 하는 프로그램으로 바꿨다.

성공한 코드는 아래와 같다.

import java.io.*;
import java.util.*;

public class sample {
    static int N, X;
    static int L, R;
    static int[] A;
    static int ans = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());
        A = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(A);
        calc(Integer.MAX_VALUE, 0, 0, 0, 0);
        bw.write(ans + "\n");
        bw.flush();
        br.close();
        bw.close();
    }

    public static void calc(int min, int max, int cnt, int idx, int sum) {
        //체크한 숫자가 2개 이상일때
        if(cnt >= 2){
            /*
              체크한 숫자들의 합이 L보다 크거나 같고, R보다 작거나 같고, 
              체크한 숫자들 중 가장 큰 수와 가장 작은수를 뺀 값이 X보다 크거나 같을 때
              ans++
            */
            if(sum >= L && sum <= R && max - min >= X){
                ans++;
            }
        }
        //루프를 돌려줌
        for(int i = idx; i < N; i++){
            calc(Math.min(min, A[i]), Math.max(max, A[i]), cnt + 1, i + 1, sum + A[i]);
        }
    }
}

 

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

16938번: 캠프 준비