백준 2798번

문제

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

2798번: 블랙잭

import java.util.Scanner;

public class Main2798 {

	public static int N;
	public static int M;
	public static int arr[];
	public static int ans[];
	public static boolean check[];
	public static int result;
	
	public static void compare(int cnt) {
		int sum = 0;

		if (cnt == 3) {						// N에서 3으로 변경
			sum = ans[0] + ans[1] + ans[2];
			
			if (sum <= M) {
				result = Math.max(sum, result);
			} 
			
		} else {
			for (int i=0; i<N; i++) {
				if (!check[i]) {					
					ans[cnt] = arr[i];
					check[i] = true;
					compare(cnt + 1);
					check[i] = false;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		
		arr = new int[N];
		ans = new int[N];
		check = new boolean[N];
		
		for (int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		
		sc.close();
		compare(0);
		
		System.out.println(result);
	}
}

1. 첫번째 시간초과 후 두번째 정답

 

2. 처음으로 시간초과로 틀린문제다. 그동안 귀찮다는 이유로 BufferedReader를 사용해오지 않았는데 이번 기회에 확실히 사용법을 익혀야겠다 다짐했다.

 

3. 다행히 주석을 달아놓은 if문에서 조건을 바꾸니 바로 통과를 했다. 이전에는 cnt의 값이 N이 될 때까지 탐색을 계속했는데 어차피 앞에서 3번째 순서까지만 더하면되기에 cnt가 3이 될때까지만 탐색을 하도록 유도했다.

 

4. 다른 사람들의 풀이 방식은 크게 3중 for문의 사용, 나와 비슷한 방식으로 풀었다. 3중 for문은 2중 for문과 방식이 크게 다르지 않기에 스킵하자.