[SWEA] 1486. 장훈이의 높은 선반 (D4 / 순조부) - Java

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw 

SW Expert Academy

 

 

 

 

문제 해석

점원이 한 명일 때 : 점원의 키
점원이 두 명 이상일 떄 : 탑을 만든 점원의 키의 합
만들 수 있는 높이가 B 이상이면서 가장 낮은 탑의 높이 구하기


- 입력
첫 번째 줄 : N B  # N = 점원 수 | B = 탑의 높이
두 번째 줄 : 점원의 키


- 출력
B를 넘는 가장 낮은 탑 - B

 

 

풀이 & 코드 해석

문제가 길지만 쉽게 정리하면 점원들의 키를 더하는 경우의 수를 구해서 B와의 차이가 가장 작은 것을 선택하는 문제입니다.

 

따라서 부분집합을 사용하면 쉽게 풀리게 됩니다.

 

부분집합의 개념이 생소하시다면 아래의 글을 참고해주세요!

 

https://angelplayer.tistory.com/399

[알고리즘] 순열, 조합, 부분 집합

 

 

 

 

코드

package month4.day05;

import java.io.*;
import java.util.*;

public class 장훈이의높은선반 {

	static int[] employee;
	static int N, B, answer;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int T = Integer.parseInt(st.nextToken());

		for (int test_case = 1; test_case <= T; test_case++) {
			// 첫 번째 줄
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); // 직원 수
			B = Integer.parseInt(st.nextToken()); // 구하고자 하는 탑의 높이

			answer = Integer.MAX_VALUE;
			employee = new int[N];

			// 두 번째 줄
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				employee[i] = Integer.parseInt(st.nextToken());
			}

			sel = new boolean[N]; // 선택 배열
			// 부분 집합
			recursive(0);

			System.out.println("#" + test_case + " " + answer);

		} // [E] test_case
	}

	static boolean[] sel;

	private static void recursive(int idx) {
		// basis
		if (idx == N) {

			int nowAnswer = 0;
			for (int i = 0; i < sel.length; i++) {
				if (sel[i] == true) {
					nowAnswer += employee[i];
				}
			}

			if (nowAnswer >= B) {
				answer = Math.min(answer, nowAnswer - B);
			}

			return;
		}

		// inductive
		sel[idx] = true;
		recursive(idx + 1);
		sel[idx] = false;
		recursive(idx + 1);

	}
}

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java