[SW Expert Academy] 3234 준환이의 양팔저울

문제

---

SW Expert Academy

SW Expert Academy

 

 

풀이방법

---

weight배열에 입력을 받고, perm함수를 사용해서 나올수 있는 경우들을 구한다. 이때, 무게추를 올려놓는 순서가 중요하므로 순열을 사용해 구한다.

 

rightleft함수를 사용해서 추를 왼쪽으로 올렸을때, 오른쪽으로 올렸을때를 구해준다.

이때 left+get[index] >= right조건과 left >= right+get[index]조건을 걸어서,  오른쪽 위에 올라가있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 커지지 않게 해준다.

 

코드

---

import java.util.Arrays;
import java.util.Scanner;

public class Solution {

	 static int weight[];
	 static int get[];
	 static boolean visit[];
	 static boolean visit2[];
	 static boolean[] select;
	 static int N,total,total2;
	 static int result;
	 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input=new Scanner(System.in);
		int T=input.nextInt();
		for(int t=0; t<T; t++) {
		N=input.nextInt();
		weight = new int[N];
		
		for(int i = 0; i<N; i++) {
			weight[i]=input.nextInt();
		}
		visit = new boolean[N];
		visit2 = new boolean[N];
		get = new int[N];

		select = new boolean[1000];
		result=0;
		perm(0);
		System.out.printf("#%d %d",t+1,result);
		System.out.println();
		}
	}
	static void perm(int cnt) {
		if(cnt==N) {
			total++;
			rightleft(0,0,0);
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(visit[i]==false) {
				visit[i]=true;
				get[cnt]=weight[i];
				perm(cnt+1);
				visit[i]=false;
				
			}
		}
	}
	
	static void rightleft(int index,int left, int right) {

		if(index==N) {
			result++;
			return;
		}
		//이 숫자를 왼쪽으로 뽑을게
		if(left+get[index] >= right) {
			rightleft(index+1,left+get[index],right);
		}
		else {
			return;
		}
		
		//이 숫자를 오른쪽으로 뽑을게
		if(left >= right+get[index]) {
			rightleft(index+1,left,right+get[index]);
		}
		else {
			return;
		}
	}
	
}