[JAVA]백준2798번 블랙잭

오늘은 백준2798번 블랙잭 문제를 풀어보도록 하자. 3중포문을 사용하면 간단하게 끝나는 문제지만 탐색노드의 깊이가 얕고 데이터 수도 많지 않아서

DFS로 구현해보았다. depth는 3으로 고정되어 있고 만일 3에 도달했다면 M값보다 작거나 같은 최댓 값을 뽑아내면 된다.

문제는 다음과 같다.

                               [접근법]

  1. 일반적인 DFS이기 때문에 생략하기로 하자 ~

                                     [코드]
import java.io.*;
import java.util.*;

public class Main {
	static int N, M, answer;
	static boolean[] visit;
	static int[] arr;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		visit = new boolean[N];
		arr = new int[N];
		
		st = new StringTokenizer(br.readLine());
		
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		select_card(0, 0, 0);
		System.out.println(answer);
	}
	
	
	static void select_card(int cnt, int value, int idx) {
		if(cnt == 3) {
			if(answer < value && value <= M) answer = value;
			return; 
		}
		for(int i=idx;i<N;i++) {
			if(!visit[i]) {
				visit[i] = true;
				select_card(cnt+1, value + arr[i], i+1);
				visit[i] = false;
			}
		}
	}
}