[SWEA] 장훈이의 높은 선반

Posted on | In |

문제 보러가기

제한사항

이외의 제한사항은 없다.

첫번째 생각

완전탐색 문제로, dfs를 사용해 최소값을 찾는다.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.Scanner;

public class Solution {
	static int fit;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1;tc<=T;tc++) {
			int N = sc.nextInt();
			int B = sc.nextInt();
			int[] p = new int[N];
			for(int i=0;i<N;i++) {
				p[i] = sc.nextInt();
			}
			fit = Integer.MAX_VALUE;
			
			go(0,p,N,0,B);
			System.out.println("#"+tc+" "+(fit-B));
		}
	}
	
	public static void go(int depth,int[] p,int N,int sum,int B) {
		if(depth==N) {
			if ( sum >= B && sum-B < fit-B) {
				fit = sum;
			}
			return ;
		}
		
		go(depth+1,p,N,sum+p[depth],B);
		go(depth+1,p,N,sum,B);
		
	}
}