[SWEA] 3234번: 준환이의 양팔저울 (Java)

문제

SWEA(SW Expert Academy) 3234번 준환이의 양팔저울 [D4]

풀이

양팔저울에 올리는 순서 정하기 => 순열

어느쪽에 올릴지 정하기 => 부분집합

무게를 입력받아 우선 올려놓을 순서를 정함.

sorted배열에 실행완료 된 순열을 저장하며, 순열이 완성되었을 경우(cnt==N) 어느쪽에 올릴지 정함.

현재 추를 오른쪽에 올리는 경우, 왼쪽에 올리는 경우를 각각 실행.

실행도중 left<right일 경우, 가지치기를 통해 시간을 단축 (백트래킹)

기저조건을 만족한 경우, 경우의 수를 증가시킨 후 종료

코드

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

public class Solution{
	static int N, res;
	static int[] weight,sorted;
	static boolean[] isSelected;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int tc = Integer.parseInt(br.readLine());
		for(int T = 1 ; T<=tc ; T++) {
			N = Integer.parseInt(br.readLine());
			weight = new int[N];
			sorted = new int[N];
			isSelected = new boolean[N];
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for(int i =0 ; i < N ; i++) {
				weight[i] = Integer.parseInt(st.nextToken());
			}
			
			res = 0;
			perm(0);
			
			sb.append("#").append(T).append(" ").append(res).append("\n");
		}
		System.out.println(sb.toString());
		br.close();
	}
	
	//왼쪽, 오른쪽 관계없이 올려놓는 순서를 정하는 '순열'함수
	private static void perm(int cnt) {
		if(cnt == N) {		//기저조건
			scale(0,0,0);
		}
		//순열 만들기
		for(int i = 0 ; i < N ; i++) {
			if(isSelected[i]) continue;
			sorted[cnt] = weight[i];		//sorted: 순열결과를 저장(인덱스 저장이 아닌 값 저장)
			isSelected[i] = true;	// 현재 인덱스 선택처리
			perm(cnt+1);	
			isSelected[i] = false;	// 선택 처리 초기화
		}
	}
	
	//순열함수의 결과값을 이용해서 양팔저울에 올릴 경우의 수를 계산하는 '부분집합'함수
	private static void scale(int cnt, int left, int right) {
		if(left<right) return;		//가지치기(현재 왼쪽의 무게보다 오른쪽의 무게가 많을 때)
		if(cnt == N) {		//기저조건
			res++;		//경우의 수 증가
			return;
		}
		scale(cnt+1, left, right+sorted[cnt]);		//오른쪽에 올렸을 때
		scale(cnt+1, left+sorted[cnt], right);		//왼쪽에 올렸을 때
	}
}