[백준_2798] 블랙잭 - JAVA

문제 출처

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

풀이

• 조합을 이용해 풀 수 있는 문제이다. 주어진 숫자 중 3개의 수를 뽑아 조합을 만든다.
• 생성된 조합의 수를 모두 더해 입력 M과의 차이를 range로 저장한다.
• range가 최소가 될 때마다, Result를 갱신한다.

코드

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

public class Main {
    static int N, M;
    static int range = Integer.MAX_VALUE;
    static int result = 0;

    static void permutation(int[] arr, boolean[] flag, int index) {
        if (index == 3) {
            int sum = 0;
            for (int i = 0; i < N; i++) {
                if (flag[i]) {
                    sum += arr[i];
                }
            }
            if (M >= sum && range > Math.abs(M - sum)) {
                range = Math.abs(M - sum);
                result = sum;
            }
            return;
        }

        for (int i = 0; i < N; i++) {
            if (flag[i]) continue;
            flag[i] = true;
            permutation(arr, flag, index + 1);
            flag[i] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        N = Integer.parseInt(stringTokenizer.nextToken());
        M = Integer.parseInt(stringTokenizer.nextToken());
        int[] arr = new int[N];
        boolean[] flag = new boolean[N];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        permutation(arr, flag, 0);
        System.out.println(result);

    }
}

채점 결과