[SWEA]1486번:장훈이의 높은 선반(JAVA)

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

---

• 알고리즘[풀이방법]

종업원들의 키를 이어붙여  선반의 높이보다 큰 최소값을 구하는 문제이다. 말은 복잡하지만 단순하게 생각하면 주어진 B보다 큰 합 중 가장 작은 값을 구하면 끝난다.

처음엔 for문을 0부터 돌려야 인덱스 별로 모든 값을 확인할 수 있다고 생각했는데, 그렇게하면 순열의 형태가 된다.  답은 잘 나오지만 시간초과가 떴다... 이 문제에서는 순서가 중요하지 않기 때문에 조합으로 풀면 된다. 매 인덱스가 돌 때마다 그 앞의 인덱스는 고려할 필요가 없기 때문에 for문은 idx값부터 계산하였다. 

여기서는 모든 종업원의 키를 더할 필요가 없기 때문에 cnt가 n보다 작더라도 합이 B이상이면 값을 확인하고 return해준다. bt로부터 계산된 min을 출력하면 끗!

---

package 김영서;

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

public class SWEA1486_장훈이의높은선반 {
	static int N, B, arr[], sum, min;
	static boolean visited[];

	static void bt(int cnt, int idx) {
		// cnt가 N보다 작을 때, sum이 B보다 크면 리턴
		// cnt가 N이면 바로 리턴
		if (cnt >= 1 && cnt < N) {
			if (sum >= B) {
				min = Math.min(sum - B, min);
				return;
			}
		}
		if (cnt == N) {
			min = Math.min(sum - B, min);
			return;
		}
	
		for (int i = idx; i < N; i++) {
			if (!visited[i]) {
				sum += arr[i];
				visited[i] = true;
				bt(cnt + 1, i);
				sum -= arr[i];
				visited[i] = false;
			}
		}

	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();

		int tc = Integer.parseInt(br.readLine());
		for (int TC = 1; TC <= tc; TC++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());
			arr = new int[N];
			sum = 0;
			min =  Integer.MAX_VALUE;
			visited = new boolean[N];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}

			bt(0, 0);
            
			sb.append("#").append(TC).append(" ").append(min).append("\n");
			
		}
		System.out.println(sb);
	}// main
}// clas