[SWEA] 1486 : 장훈이의 높은 선반

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AV6kld8aisgDFASb&contestProbId=AV2b7Yf6ABcBBASw&probBoxId=AV_W57U6ACQDFAX7&type=PROBLEM&problemBoxTitle=A%ED%98%95+%EC%A4%80%EB%B9%84+%EB%AC%B8%EC%A0%9C&problemBoxCnt=4 

SW Expert Academy

쉽게 풀었는데 계속 시간초과가 나서 당황스러웠음.

DFS로 구현한 메소드에서 for문의 시작을 잘못 설정했다. 고쳤더니 통과!

탑의 최댓값을 Integer.MAX_VALUE로 설정했을 때와 직접 모든 키를 합한 수로 설정해주었을 때 크진 않지만 후자가 메모리사용이 적고 시간이 짧았다.

 

내 코드

메모리 : 18744 KB

시간 : 109 ms

코드길이 : 1538 B

 

[내 코드]

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

public class Solution {
	static int N;
	static int B;
	static int[] height;
	static int result;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			sb.append('#').append(t).append(' ');
			
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());
			
			height = new int[N];
			boolean[] selected = new boolean[N];
			
			st = new StringTokenizer(br.readLine());
			int max = 0;
			for(int n = 0; n < N; n++) {
				height[n] = Integer.parseInt(st.nextToken());
				max += height[n];
			}
			result = max;
			
			for(int n = 0; n < N; n++) {
				selected[n] = true;
				search(n, selected, height[n]);
				selected[n] = false;
			}
			sb.append(result).append('\n');
		}
		System.out.print(sb);
	}
	
	public static void search(int Index, boolean[] selected, int top) {
		if(top >= B) {
			result = Math.min(Math.abs(B - top), result);
			if(result == 0)
				return;
		}
		else {
			for(int n = Index + 1; n < N; n++) {
				//선택 안된 데이터면
				if(!selected[n]) {
					//선택해준 후
					selected[n] = true;
					search(n, selected, top + height[n]);
					selected[n] = false;
				}
			}
		}
		return;
	}
	
}