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

SW Expert 1486. 장훈이의 높은 선반

 

* 문제의 저작권은 SW Expert에 있습니다.

 

 

 

 

 

 

[문제 접근]

 

점원의 키를 포함하는 경우도 있고 포함하지 않는 경우도 있기 때문에 DFS로 풀었다.

문제를 제대로 안읽어서 무조건 주어진 높이와 탑의 높이가 작은 경우를 구하는건 줄 알았는데

높이가 주어진 값보다 작은 경우는 만들 수 없다는 조건이 있기 때문에 Math.abs를 안해줘도 된다.

 

 

 

 

[코드]

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

public class Solution_1468 {
	static int N, B;
	static int[] heights;
	static int min;
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int test_case = 1; test_case <= T; test_case++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());
			heights = new int[N];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < heights.length; i++) {
				heights[i] = Integer.parseInt(st.nextToken());
			}
			
			min = Integer.MAX_VALUE;
			dfs(0, 0);
			System.out.println("#"+test_case + " " + min);
		}
	}

	static void dfs(int height, int depth) {
		if (depth+1 >N) {
			if (height >= B) {
				if ((Math.abs(height-B))<min) {
					min = Math.abs(height-B);
				}
			}
			return;
		}
		dfs(height+heights[depth], depth+1);
		dfs(height, depth+1);
	}
}