[백준] 16938: 캠프 준비 - JAVA

02 Jun 2023 in Algorithm on 브루트포스 알고리즘

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

풀이

비트마스크를 이용해 조합을 만드는 문제였다.

조합을 만들어 문제의 조건들을 비교해주었다.

비트마스크 조합

int N = 3;
int[] arr = {1, 2, 3}

for(int i = 1; i < (1 << N); i++) {

    for(int j = 0; j < N; j++) {
        if((i & (1 << j)) != 0) {
            System.out.print(arr[j] + " ");
        }
    }

    System.out.println();
}

공집합을 제외하고 1~7까지 탐색한다.

예를 들어 6을 탐색하면 2진수로 6은 110이므로

배열에서 1번, 2번 인덱스의 값을 꺼낸다.

---

메모리: 14288KB

시간: 128ms

언어: Java 11

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int ans = 0;
        for (int i = 1; i < (1 << N); i++) {
            int len = 0;
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            int sum = 0;

            for (int j = 0; j < N; j++) {
                if ((i & (1 << j)) != 0) {
                    len++;
                    max = Math.max(arr[j], max);
                    min = Math.min(arr[j], min);
                    sum += arr[j];
                }
            }

            if (len == 1) { // 문제는 두 문제 이상이어야 한다
                continue;
            }
            if (sum < L || sum > R) { // 문제 난이도의 합은 L보다 크거나 같고, R보다 작거나 같아야 한다
                continue;
            }
            if (max - min < X) { // 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이는 X보다 크거나 같아야 한다
                continue;
            }

            ans++;

        }

        System.out.println(ans);

    }

}