[백준] 2798번 블랙잭(JAVA)

문제

- 카지노 게임 블랙잭의 규칙은 카드의 합이 21을 넘지 않는 한도 내에서 카드의 합을 최대한 크게 만드는 것

- 블랙잭 고수 김정인이 만든 새로운 규칙의 블랙잭은 딜러가 외친 숫자 M을 넘지 않으면서 M과 최대한 가깝게 카드의 합을 구성하는 것

- N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력

- N(3<=N<=100) : 카드의 개수

- M(10<=M<=300,000) : 딜러가 외치는 수

 

해결방법

카드를 3장 고르고 해당 카드의 합이 M에 최대한 가까운 경우에 출력을 하는 것이므로, 카드를 3장 선택하는 것부터 생각을 했다. 카드를 3장 선택하는 과정은 중복 없이 각각을 선택하는 것이기 때문에 조합으로 숫자 3개를 선택하는 방법으로 코드를 작성하였다.

조합과 관련된 내용은 이전에 포스팅한 내용을 참고하면 좋을 것 같다.

[알고리즘] 조합(Combination)

재귀로 함수를 구현하였는데 카드가 3개가 뽑히면 3개의 수의 합이 M과 가장 가까운 숫자들인지 조건 검사를 해본 뒤 return할 수 있도록 함수를 구현하였다.

 

코드

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

class Main{
    static int N, M, dif, result;		// 카드 개수, 딜러가 외친 수, 차이, 출력될 값
    static int[] card, black;			// 카드 배열, 블랙잭에 포함될 숫자 배열
    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());	// 딜러가 외친 수
       card = new int[N];			// 카드 배열
       black = new int[3];			// 블랙잭에 포함될 숫자 배열
       dif = Integer.MAX_VALUE;			// 숫자들의 합과 M의 차이
       result = 0;				// 출력될 값

       st = new StringTokenizer(br.readLine(), " ");
       for(int i = 0; i<N; i++){
           // 카드 숫자 입력 받기
           card[i] = Integer.parseInt(st.nextToken());
       }

       com(0, 0);	// 조합

        System.out.println(result);

       br.close();
    }

    // 여러 개의 카드 중 3장을 뽑는 조합
    static void com(int cnt, int start){
        if(cnt == 3){
            int sum = 0;
            for(int i = 0; i<3; i++){
                sum += black[i];	// 뽑은 카드 3장의 합 구하기
            }
            // 뽑은 카드 3장의 합이 M을 넘지 않으면서 이제까지 뽑았던 조합 중 차이가 가장 적다면
            if(M-sum >= 0 && M-sum < dif){
                result = sum;	 	// 합을 출력될 변수에 저장
                dif = M-sum;		// 차이는 계속해서 비교해야 하기 때문에 갱신
            }
            return;
        }
		
        // 조합 코드(한 자리에 대해서 숫자를 뽑고 그 다음 자리에 대해서 숫자 뽑기)
        for(int i = start; i<N; i++){
            black[cnt] = card[i];	
            com(cnt+1, i+1);
        }
    }
}