[Java] Baekjoon 2798番 ブラックジャック

1. 問題と条件

問題

ブラックジャックはカードの合計が21を超えない限り、カードの合計を最大限に大きくするゲームだ。

N枚のカードに書いてる数字が与えられた時、Mを超えないながらMにできるだけ近いカード3枚の合計を求めて出力してください。

入力

最初の行にカードの数N（3≦N≦100）とM（10≦M≦300,000）が与えられます。

2行目にはカードに書かれている数が与えられ、この値は100,000を超えない正の整数である。

合計がMを超えないカード3枚を見つけることができる場合のみ入力として与えられる。

出力

Mを超えずにMに近いカード3枚の合計を出力する。

2. 説明

　この問題はブラックジャック条件を活用し変更した問題で、N枚のカードから3枚のカードを選択して合計がMより小さい組み合わせの中で最大値を探す問題です。正確な最大値を探す為にはたまには無知な方法が最善の場合があります。こう言う時使う方法が「Brute force」アルゴリズムです。

　Brute forceとは英語そのまま翻訳すると「乱暴な力」の意味で、リソース（時間、メモリなど）を無知にたくさん使って欲しい値を探す徹底的な検索アルゴリズムです。理論的に可能な全てのケースの数を検索するため、欲しい値を100％探せる長所がありますが、複雑な問題にこのアルゴリズムを使う場合大量のメモリ使用と時間の浪費を引き起こすので、考えて使う必要があります。

3. 解決方法

블랙잭 설명

1. Mの範囲が10 ≤ M ≤ 300,000であるため、三つのカードを選ぶ場合の最小値は30なので30以下の値を現在状態の最大値と指定します。（個人的には0が楽なので０に設定しました。）

2. 1枚目のカードを選びます。1〜N-2範囲のカードを選択します。

3. 2枚目のカードを選びます。1枚目のカードの次のカードからN-1までのカードを選択します。

4. 3枚目のカードを選びます。2枚目のカードの次のカードからNまでのカードを選択します。

5. 3枚のカードを全て選択して合計を出します。出した値がMより大きい場合は検査しません。Mより小さい場合は現在の最大値と3枚のカードの合計を比べて、現在の最大値が3枚のカードの値より小さい場合最大値を変更します。

6. 全ての反復が終了した場合、最後の最大値を返します。

4. コード

import java.util.Scanner;

class Main {
	public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String line1 = sc.nextLine();

        int N = Integer.parseInt(line1.split(" ")[0]);
        int M = Integer.parseInt(line1.split(" ")[1]);

        String line2 = sc.nextLine();
        int[] cards = new int[N];

        for(int i=0;i<N;i++){
            cards[i] = Integer.parseInt(line2.split(" ")[i]);
        }

        sc.close();

        System.out.println(blackjeak(cards, M));
    }

    private static int blackjeak(int[] cards, int M){
        int max = 0;

        for(int i=0;i<cards.length-2;i++){
            for(int j=i+1;j<cards.length-1;j++){
                for(int k=j+1;k<cards.length;k++){
                    int value = cards[i]+cards[j]+cards[k];

                    if(value <= M && max < value) max = value;
                }
            }
        }

        return max;
    }
}