[BOJ - JAVA] 2798 - 블랙잭(브루트포스, 백트래킹)

# 주소

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

2798번: 블랙잭

 

# 문제

 

# 문제 해설 및 코드 리뷰

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

public class Main{
    static int[] arr;
    static int n;
    static int m;
    static boolean visit[];
    static int max = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();

        StringTokenizer st = new StringTokenizer(s," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        visit = new boolean[n];
        arr = new int[n];
        s = br.readLine();
        st = new StringTokenizer(s, " ");
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        dfs(0, 0);   
        System.out.println(max);
        
    }
    public static void dfs(int t, int sum){
        if(t == 3){
        	if(sum <= m){
                max = Math.max(max, sum);
            }
            return;
        }
        for(int i = 0; i < n; i++){
            if(!visit[i]){
                visit[i] = true;
                dfs(t + 1, sum + arr[i]);
                visit[i] = false;
            }
        }
    }
}

백트래킹으로 풀이를 하려고 했는데 기존의 코드랑 큰 차이는 없습니다. 

근데 자꾸만 시간초과가 떠서 뭘까.. 뭘까 고민하다가 return을 if 문이 끝나고 넣으니까 잘 작동하네요

시간제한 거는거 참 까다로운거 같습니다.. ㅠㅠㅠㅠ

원래는 Scanner로 풀려고 했는데 시간초과 나서 Buffered로 다 바꾼 코드입니다.

그리고 n과 m은 띄어쓰기를 하고 받아야 하므로 StringTokenizer로 n과  m을 입력받습니다.

boolean타입의 visit을 선언하고 arr에 Integer를 입력받습니다!

 

늘 그렇듯 dfs(0,0)을 실행하되 dfs의 인자 2개는 정수형으로 입력받습니다.

하나는 index값인 t, 하나는 블랙잭의 세 카드의 합이될 sum입니다!

그리하여 t가 3이 될 때 sum이 m보다 작거나 같은 전제하에 max에 값을 담습니다. 

단, max에 들어가는 값은 sum과 기존의 max값과 비교하여 큰 값을 넣도록 합니다.

(여기서 시간초과가 났습니다. arraylist에 합들을 다 담고 arraylist를 정렬해서 가장 큰 값을 

답으로 출력하려고 했는데,,,)

이후 return하여 재귀함수로 돌아오면 되겠습니다.

어려운 문제는 전혀 아닙니다. 다만 늘 시간초과 때문에 애먹는거같네요... 오늘도 화이팅

감사합니다