[ SWEA ] 3234 준환이의 양팔저울 D4 (JAVA)

---

---

문제 이해

1. 모든 무게 추를 양팔저울 위에 올리는 순서는

총 N!가지

2. 양팔저울의 왼쪽에 올릴 것인지 오른쪽에 올릴 것

인지를 정해야 해서 총 2N * N!가지의 경우

3. 오른쪽 위에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 커져서는 안 된다.

 

아이디어

1. N개의 추를 순열로 먼저 구한다.(누가봐도 순열임)

2. 1개의 순열이 완성되면 다시 부분집합을 활용해서,

선택/비선택 순으로 재탐색을 한다.

3. 선택은 왼쪽이 오른쪽보다 크면 선택하도록 한다.

 

코드

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

public class Solution {
	static int N, totalCnt;
	static int[] input;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Int(br.readLine());								//테케 입력
		for (int tc = 1; tc <= T; ++tc) {						//테케만큼 반복
			N = Int(br.readLine());								//개수 입력
			totalCnt = 0;										//전체 카운트 초기화
			input = new int[N];									//입력 배열 할당
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < N; ++i) input[i] = Int(st.nextToken());
			permutation(0, new boolean[N], new int[N]);			//수열생성 호출
			sb.append("#").append(tc).append(" ").append(totalCnt).append('\n');
		}
		System.out.println(sb);									//출력
	}

	static void permutation(int cnt, boolean[] isSelected, int[] nums) {
		if (cnt == N) {											//다뽑았으면 계산
			calculate(0, nums, 0, 0);						
			return;
		}
		for (int i = 0; i < N; ++i) {							//수열 생성
			if (!isSelected[i]) {
				isSelected[i] = true;							
				nums[cnt] = input[i];
				permutation(cnt + 1, isSelected, nums);
				isSelected[i] = false;
			}
		}
	}
																//계산 메소드(부분집합)
	static void calculate(int cnt, int[] nums, int left, int right) {
		if (cnt == N) {											//다 뽑았으면
			++totalCnt;											//카운팅
			return;
		}
		if (left >= right + nums[cnt]) 							//left 값보다 크면 넣어준다.
			calculate(cnt + 1, nums, left, right + nums[cnt]);	//선택시 오른쪽 저울에
		calculate(cnt + 1, nums, left + nums[cnt], right);		//비 선택시 왼쪽 저울에
	}

	static int Int(String s) {									//Int변환 후 반환
		return Integer.parseInt(s);
	}
}

---

CPDM