백준 16938번(Java)

예제 입력과 답은 아래와 같다.

3 5 6 1
1 2 3

2

자세한 건 직접 가서 보자.
https://www.acmicpc.net/problem/16938

문제를 보고 백트랙킹으로 완전탐색으로 풀어도 될 거 같아서 구상을 해봤다.

다음과 같이 진행을 해보자

1. 문제의 난이도를 하나씩 방문한다. 방문한 문제는 모두 더해주고 방문처리를 해준다.
2. 만약 모두 더한 값이 l 혹은 r의 범위를 벗어나지 않고 방문한 문제의 크기가 문제에서 제시한 최소 2문제 이상이라면 방문한 문제의 난이도의 최솟값과 최댓값의 차이가 x 이상일 경우, cnt를 증가시켜준다.
3. 백트래킹이 종료되면 cnt를 출력하고 종료한다.

코드는 다음과 같다

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

public class Main {
    static int n, x;
    static long l, r;
    static int[] num;
    static boolean[] visited;
    static int cnt;

    static void func(int depth, int sum, int size){
        if(l <= sum && sum <= r && size >= 2){
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            for(int i = 0; i < n; i++){
                if(visited[i]) {
                    min = Math.min(min, num[i]);
                    max = Math.max(max, num[i]);
                }
            }

            if(max - min >= x)
                cnt++;
        }

        for(int i = depth; i < n; i++){
            if(!visited[i]){
                visited[i] = true;
                func(i + 1, sum + num[i], size + 1);
                visited[i] = false;
            }
        }
    }
    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 = Long.parseLong(st.nextToken());
        r = Long.parseLong(st.nextToken());
        x = Integer.parseInt(st.nextToken());

        num = new int[n];
        visited = new boolean[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++)
            num[i] = Integer.parseInt(st.nextToken());

        func(0, 0, 0);

        System.out.println(cnt);
    }
}

아직 블로깅 못한 문제들이 많다. 최근에 알고리즘 문제를 풀지 않아서 감이 많이 죽었다. 다시 감도 살리고 블로깅도 할겸 이렇게 문제풀이를 해야겠다.

끝!