[BAEKJOON_2798 - JAVA] 블랙잭

문제

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

2798번: 블랙잭

 

 

과정

1.  시작 index, 뽑은 카드수, 카드의 합을 매개변수로 하는 DFS 함수 호출.
2. M을 넘을 경우 가지치기
3. 3가지 카드를 뽑은 경우 max값과 비교 후 기존의 값보다 큰 경우 갱신

 

 

풀이

• 기존에 풀었던 문제를 DFS로 풀이. ( 기존에는 for문으로 풀이.)

 

 

알고리즘 지식

• DFS

 

 

JAVA코드

package BJ_200624;

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

// 카드 3장의 합이 M에 가장 가까운 수
public class BJ2798_블랙잭 {

	static int N, M; // N장의 카드 , 대상이 되는 수 M
	static int max; // M에 가장 가까운 수를 보관
	static int[] cards; // 카드를 담을 배열
	static boolean[] visited; // 카드 중복체크를 위한 배열

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		// input & init
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		cards = new int[N];
		visited = new boolean[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			cards[i] = Integer.parseInt(st.nextToken());
		}
		// end of input

		//dfs
		for (int i = 0; i < N; i++) {
			visited[i] = true;
			dfs(i, 0, cards[i]);
			visited[i] = false;
		}
		
	}

	private static void dfs(int start, int cnt, int val) {
		// 값이 M을 넘은 경우
		if (val > M) {
			return;
		}

		// 3개를 뽑은 경우
		if (cnt == 2) {
			max = Math.max(max, val); // 값 비교후 max 갱신
			return;
		}

		// card 뽑기
		for (int i = start; i < N; i++) {
			// 방문한 경우
			if (visited[i]) { 
				continue;
			}
			visited[i] = true;
			dfs(i + 1, cnt + 1, val + cards[i]);
			visited[i] = false;
		}

	}

}