[백준] 2798 - 블랙잭

브루트포스 - DFS로, 전체 겹치지 않는 부분집합(원소 3개)을 만들어 모두 비교해 봐야 한다.

DFS를 통해 겹치지 않는 원소의 집합 찾는 방법은 항상 유용하니 외우자.

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

public class Main {

    static int[] arr;
    static int[] tmp;
    static int max;
    static int M;

    public static void DFS(int L, int S) {
        if (L == 3) {
            int sum = 0;
            for (int i = 0; i < 3; i++) {
                sum += tmp[i];
            }
            if(sum <= M) {
                max = Math.max(max, sum);
            }
        } else {
            for (int i = S; i < arr.length; i++) {
                tmp[L] = arr[i];
                DFS(L + 1, i + 1);
            }
        }
    }

    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());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N];
        tmp = new int[3];
        max = Integer.MIN_VALUE;

        st = new StringTokenizer(br.readLine(), " ");

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

        DFS(0, 0);
        System.out.println(max);
    }
}