[Java/자바] - 백준(BOJ) 16938번 : 캠프 준비

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

16938번: 캠프 준비

 

모든 경우의 수를 탐색하면서 최대 점수를 넘길 경우 프루닝 해주는 브루트포스(BrueteForce) + 백트래킹(BackTracking) 문제

n, l, r, x는 재귀함수를 이용하면서 자주 쓰이므로 전역변수로 초기화 하였다.

for문을 이용해 첫번째 인자를 골라서 넣고, 그 이후 첫번째 인자의 다음 인덱스부터 for문을 돌린다

이 때 sum을 체크해 r을 넘어가면 재귀함수를 실행하지 않는다.

매번 재귀할 때 마다 max, min을 조정하며 sum이 l 이상이고 max-min이 x 이상이면 ret을 증가시켜

배열에 끝에 도달하면 ret을 return하도록 하였다. 

 

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

public class Main {
    public static int n, l, r, x;
    public static int[] arr = new int[15];
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(bf.readLine());
        for (int i=0; i<n; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        int answer = 0;
        for (int i=0; i<n; i++)
            answer += Back(arr[i], i+1, arr[i], arr[i]);
        System.out.println(answer);
    }

    public static int Back(int sum, int index, int min, int max) {
        int ret = 0;
        max = Integer.max(arr[index-1], max);
        min = Integer.min(arr[index-1], min);

        if (l <= sum && max-min >= x)
            ret += 1;

        if (index == n)
            return ret;

        for (int i=index; i<n; i++) {
            if (sum + arr[i] <= r)
                ret += Back(sum+arr[i], i+1, min, max);
        }
        return ret;
    }
}