[브루트 포스] 백준 2798. 블랙잭

https://github.com/SUNGIN99/JavaCodingTest/tree/main/%EB%B0%B1%EC%A4%80/Bronze/2798.%E2%80%85%EB%B8%94%EB%9E%99%EC%9E%AD

블랙잭을 룰로 m숫자에 가장 가까운 3개의 카드 조합을 만들어야함..

DP 문제인가 해서 한참 고민하다가 도저히 답이 안 나올거 같아서 문제 유형을 보니 브루트포스라는 힌트를 얻음.

브루트 포스이므로 전체 탐색을 진행 시키도록 함.

case 1

카드 3개를 중복없이 선택하는 경우의 수

• 5 6 7, 5 6 8, 5 6 9
• 6 7 8, 6 7 9, 6 8 9
• 7 8 9

첫 카드는 반드시 전체 카드의 수 n 중에서 n-3 번째 카드만선택 가능하도록 한다.

ex) n = 5 일경우, 인덱스 : 0, 1, 2, 3, 4 이므로 0, 1, 2 까지만 선택해야 Out of Index를 일으키지 않음.

여기에 추가로 카드 3개 선택 후 숫자 합이 m보다 작거나 같고, m과의 차이가 가장 낮은 기준을 지정해주었다.

if (count == 0){
	if(m - value >= 0 && check >= m - value){
		check = m - value;
		result = value;
    }
}

코드

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

public class BackJoonMemo {
    static int[] cards;
    static boolean[] visited;
    static int n, m, result, check;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 카드의 개수 n
        n = Integer.parseInt(st.nextToken());

        // 만들어야할 숫자 m
        m = Integer.parseInt(st.nextToken());

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

        // 카드목록 cards
        cards = new int[n];

        // dfs 방문 기록
        visited = new boolean[n];

        check = Integer.MAX_VALUE;
        for(int i = 0; i<n; i++){
            cards[i] = Integer.parseInt(st.nextToken());
        }
		// 0 ~ n-3 까지의 숫자만 선택하여 길이를 넘지 않는 3개의 카드를 고르기 위한 범위
        for(int i = 0; i<n-2; i++){
            dfs(cards[i], i, 2);
        }
        System.out.println(result);

    }

    public static void dfs(int value, int index, int count){
        visited[index] = true;
        if (count == 0){
        // 카드를 3장 고르고, 외친 숫자 m에 가장 가까운 기준을 고르기 위함
            if(m - value >= 0 && check >= m - value){
                check = m - value;
                result = value;

                //System.out.println(value + ", " + index + ", " + count + ", " + Arrays.toString(visited));
            }

            visited[index] = false;
            return;
        }
		
        // 이미 고른 코드 다음 부터 지정하여 중복을 방지
        for(int i = index + 1; i< n; i++){
            if(!visited[i]){
                dfs(value + cards[i], i, count - 1);
            }
        }

        visited[index] = false;

    }


}