2798 블랙잭(완전탐색,브루트포스) Java(DFS)

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

2798번: 블랙잭

DFS로 문제풀이를 했는데 다른사람 블로그에서 값을 static으로 관리하는것과 sum의 값을 배열형식으로 관리하면 편하다는걸 알았다.

그리고 방문여부 체크를 하는 visit boolean값의경우 대부분은 필수인듯하다...

참고한 풀이주소

https://hidelookit.tistory.com/77

[백준 2798] 블랙잭 (자바)

 

public class blackjack {
	//N장의 카드
	//M을 넘지않으면서 M에 가장 가까운 숫자를 만드는 카드를골라야한다.
	private static int N=5; //카드갯수.
	private static int M=21; //목표숫자	21>=result
	private static int[] array= {5,6,7,8,9};//해당 카드를 가지고 모든경우의수를 찾아본 다음 21과 가장 가까운 숫자를가진 카드3개의 합을 구한다.
	private static boolean[] visit;
	private static int sum = 0; //가장M과 가까운 총합결과
	private static int[] result = new int[3];

	public static void main(String[] args) {
		int depth =0; //첫번째 숫자부터 시작
		visit = new boolean[N]; //방문여부 체크
		dfs(depth);

	}
	private static void dfs(int depth) {
		//종료조건 3일때 result값과 M의 값을 비교해야함
		if(depth==3) {
			int hap = 0;
			for (int i : result) {
				hap += i;
			}

			if (hap > M) {
				return;
			}
			
			if (hap <= M) {
				sum = Math.max(sum, hap);
			}
		}else {
			
			for (int i=depth; i<N; i++) {
				//현재 번호에 방문처리가 안되어있는경우
				if (!visit[i]) {
					visit[i] = true;
					result[depth] = array[i];
					dfs(depth+1);
					visit[i] = false;
				}
			}
		}
		
		
	}
}