블랙잭을 룰로 m숫자에 가장 가까운 3개의 카드 조합을 만들어야함..
DP 문제인가 해서 한참 고민하다가 도저히 답이 안 나올거 같아서 문제 유형을 보니 브루트포스라는 힌트를 얻음.
브루트 포스이므로 전체 탐색을 진행 시키도록 함.
카드 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;
}
}