[BOJ] 2798번 블랙잭

문제

www.acmicpc.net/problem/2798

2798번: 블랙잭

풀이

1) 삼중 포문

import java.io.*;
import java.util.*;

public class Main {
	static int min = Integer.MAX_VALUE;
	static int closest_for(int[] cards, int N, int M) {
		for(int i=0;i<N-2;i++) {
			for(int j=i+1;j<N-1;j++) {
				for(int k=j+1;k<N;k++) {
					if(M>=cards[i]+cards[j]+cards[k])
						min = Math.min(min, Math.abs(M-(cards[i]+cards[j]+cards[k])));
				}
			}
		}
		return M-min;
	}
	public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	StringBuilder sb = new StringBuilder();
    	int N, M, cards[];
    	
 
    	st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	cards = new int[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++)
    		cards[i] = Integer.parseInt(st.nextToken());
    	//계산
    	//삼중 포문
    	System.out.println(closest_for(cards,N,M));	
	}
} 

2) DFS

import java.io.*;
import java.util.*;

public class Main {
	static int min = Integer.MAX_VALUE;
	static int[] tmp;
	static boolean[] visited;
	static void dfs(int[] cards,int st, int depth, int N, int M) {
		if(depth==3) {
			int sum=0;
			for(int i=0;i<3;i++)
				sum+=tmp[i];
			if(M>=sum)
				min = Math.min(min, M-sum);
			return;
		}
		for(int i=st;i<N;i++) {
			if(!visited[i]) {
				tmp[depth] = cards[i];
				visited[i] = true;
				dfs(cards,st+1,depth+1,N,M);
				visited[i] = false;	
			}
		}
	}
	public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	StringBuilder sb = new StringBuilder();
    	int N, M, cards[];
    	
 
    	st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	cards = new int[N];
    	tmp = new int[3];
    	visited = new boolean[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++)
    		cards[i] = Integer.parseInt(st.nextToken());
    	//계산
    	//dfs 재귀
    	dfs(cards,0,0,N,M);
    	System.out.println(M-min);
    
	}
} 

3) 효율 코드

import java.io.*;
import java.util.*;

public class Main {
	static int closest_for(int[] cards, int N, int M) {
		int max = -1;
		for(int i=0;i<N-2;i++) {
			if(cards[i]>M)
				continue;
			for(int j=i+1;j<N-1;j++) {
				if(cards[i]+cards[j] > M)
					continue;
				for(int k=j+1;k<N;k++) {
					if(M==cards[i]+cards[j]+cards[k])
						return cards[i]+cards[j]+cards[k];
					if(M>cards[i]+cards[j]+cards[k])
						max = Math.max(max, cards[i]+cards[j]+cards[k]);	
				}
			}
		}
		return max;
	}
	public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	StringBuilder sb = new StringBuilder();
    	int N, M, cards[];
    	
 
    	st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	cards = new int[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++)
    		cards[i] = Integer.parseInt(st.nextToken());
    	//계산
    	//삼중 포문
    	System.out.println(closest_for(cards,N,M));	
	}
}