[Java] SWEA / 준환이의 양팔저울 / 3234번

[Java] SWEA / 준환이의 양팔저울 / 3234번

문제

준환이의 양팔저울 문제 링크

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

접근 방식

1. 무게추 배열을 순열로 만드는데 이 때 중복된 값을 가진 배열이 들어올 때 이를 카운트하지 않도록 next Permutation으로 순열을 구한다
2. 구한 순열 각각에 대해 왼쪽에 보낼지 오른쪽에 올릴지를 정하는 부분집합 알고리즘을 사용하여 모든 경우의 수를 탐색하되 오른쪽 합이 더 커졌을 때 가지치기를 해준다
3. 모든 무게추를 저울에 올렸을 때 카운팅 한다

코드

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

public class Solution_3234 {

	static int cntCase;
	static int T,N;
	static int[] weights;
	public static void main(String[] args) throws IOException{
		
		// ==================== 입력 =====================
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
	
		
		for(int tc=1; tc<=T;tc++) {
			N = Integer.parseInt(br.readLine());
			weights = new int[N];
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			for(int i=0;i<N;i++) {
				weights[i] = Integer.parseInt(st.nextToken());
			}
			
			cntCase = 0;
			
			
			// ================ 솔루션 =====================
			Arrays.sort(weights);
			
			// 무게추 배열의 순서를 순열로 구한 뒤 왼쪽 오른쪽으로 나누기 
			do {
				subSet(0,0,0); // 부분집합 사용
			}while(np());
			
			// ================ 출력 =====================
			sb.append("#"+tc+" "+cntCase+"\n");
		}
		
		System.out.print(sb);
	}
	
	// 무게추 배열을 순서대로 왼쪽을 선택하거나 오른쪽을 선택하되 오른쪽에 가지치기 적용
	public static void subSet(int cnt, int leftSum, int rightSum) {
		// 오른쪽 무게의 총합이 커지지 않으면서 무게추를 모두 올렸을 때 카운트 증가
		if(cnt == N) {
			cntCase++;
			return;
		}
		
		subSet(cnt+1,leftSum + weights[cnt],rightSum);
		
		if(leftSum < rightSum + weights[cnt]) return; // 가지치기
		subSet(cnt+1,leftSum,rightSum + weights[cnt]);
		
	}
	
	// next permutation으로 중복있는 배열의 순열 만들 때 같은 배열이 있는 것을 방지한다
	public static boolean np() {
		int i = N-1;
		
		while(i >= 1 && weights[i-1]>= weights[i]) --i;
		
		if(i == 0) return false;
		
		int j = N-1;
		while(weights[i-1]>= weights[j]) j--;
		
		swap(i-1,j);
		
		int k = N-1;
		while(i<k) swap(i++,k--);
		
		return true;
		
	}
	
	public static void swap(int a, int b) {
		int temp = weights[a];
		weights[a] = weights[b];
		weights[b] = temp;
	}

}