[자바]백준 2798번 블랙잭 [브루트포스][엄탱]

문제 링크

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

2798번: 블랙잭

문제 설명

블랙잭은 기준 점수를 21에 가깝게 최대한 카드의 합을 크게 만드는 게임이다.

이 문제에서는 블랙잭의 기준 점수를 랜덤 하게 주고 주어진 수들에서 3장을 뽑아 기준 점수에 가깝게 최대한의 카드의 합을 구하는 문제이다.

해설

해당 문제는 알고리즘 분류가 브루트포스 알고리즘으로 되어 있다.

또한, 입력에서 보면 카드의 개수가 100 이하여서 완전탐색을 진행하더라도 총경우의 수가 1억 번을 넘지를 않는다.

따라서 완전탐색으로 풀어도 무방하다고 생각한다.

이 문제는 완전탐색으로 3중 for문을 돌려주어서 카드 3장이 될 수 있는 모든 경우의 수를 다 더해주고 비교해 주면 된다.

코드

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

public class Main {
    static int N;
    static int M;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine(), " ");
        
        int[] arr = new int[N];
        
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        System.out.println(addLargeNumberSearch(arr));
        
        br.close();
    }
    
    public static int addLargeNumberSearch(int[] arr) {
        int result = 0;
        
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                for (int k = j + 1; k < arr.length; k++) {
                    int num = arr[i] + arr[j] + arr[k];
                    
                    if (num < M) {
                        result = Math.max(result, num);
                    } else if (num == M) {
                        return M;
                    }
                }
            }
        }
        
        return result;
    }
}