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

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw

SW Expert Academy

1. 주의할 점

- 2가지의 조건을 통해 TLE를 예방한다

  1) 저울에 올릴 때, 오른쪽의 총합 > 왼쪽의 총합이 된다면 무조건 왼쪽에만 추가한다

  2) 남은 저울을 모두 오른쪽에 올려도 오른쪽의 총합<= 왼쪽의 총합일때 경우의 수를 계산해서 추가한다

 

2. 구현

- 숫자를 입력 받으면서, 무게의 총합을 미리 구해놓는다

- DFS는 4가지의 매개변수를 요구하며 차례대로 올린 추의 개수(Idx), 왼쪽 저울의 총합(Lsum), 오른쪽 저울의 총합(Rsum), 남은 추의 총합(Tot)이다

- 첫 번째 If문 Remain + Rsum <= Lsum 을 통해 남은 추들을 전부 오른쪽에 올려도 상관없는 경우, 모든 경우의 수를 계산하여 더한다. 경우의 수로는 남은 추들을 왼쪽 or 오른쪽에 넣을것인가(x2), 올려놓는 순서는 어떻게 할 것인가(남은 추의 개수!)

- 2 번째 If문을 통해 모든 추를 올려놓았을 때 Result++한다

- For문을 통해 현재 저울에 올릴 추를 오른쪽에 넣었을때 Rsum+Arr[i]<=Lsum이 된다면 오른쪽에도 넣을 수 있도록 한다

 

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

public class Solution_d4_3234_준환이의양팔저울 {
	static int num,arr[],result,order[],tot;
	static boolean check[];
	
	static void dfs(int idx,int lsum, int rsum, int remain) {
		if(lsum>=rsum+remain) {
			int cnt=1;
			//남은 수들을 양쪽 어디에 넣어도 상관이 없다
			for(int i=0;i<num-idx;i++)
				cnt*=2;
			//남은 수들을 넣는 순서
			for(int i=1;i<=num-idx;i++)
				cnt*=i;
			result+=cnt;
			return;
		}
		
		if(idx==num) {
			result++;
			return;
		}
		for(int i=0;i<num;i++) {
			if(!check[i]) {
				check[i]=true;
				if(rsum+arr[i]<=lsum) 
					dfs(idx+1,lsum,rsum+arr[i],remain-arr[i]);
				dfs(idx+1,lsum+arr[i],rsum,remain-arr[i]);
				check[i]=false;
			}
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test= Integer.parseInt(br.readLine());
		for(int t=1;t<=test;t++) {
			num = Integer.parseInt(br.readLine().trim());
			//초기화
			arr = new int[num];
			order = new int[num];
			result=0;
			check = new boolean[num];
			tot=0;
			
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str);
			for(int i=0;i<num;i++) {
				arr[i]=Integer.parseInt(st.nextToken());
				tot+=arr[i];
			}
			dfs(0,0,0,tot);
			System.out.println("#"+t+" "+result);
		}
	}
}