3234. 준환이의 양팔저울

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw 

SW Expert Academy

1. 1,2,4 가 들어오면 순열을 만들어준다. ex)1,2,4 / 1,4,2 ......

2. 그 순열을 가지고 dfs를 돈다

3.dfs : (1,2,4)에 대해 왼쪽,오른쪽 분기로 dfs2개 돌린다.

3-1 : 이때 depth를 인덱스로 사용하라

3-2 : left<right -> 유망X -> return (가지치기)

3-3: depth==3 -> return, 더탐색X, 정답++

 

 

 

 

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 answer;
	static int N;
	static boolean[] visit;
	static int[] result;
	static int[] arr;
	
	/*
	 * 왼무게, 오른무게
	 * 정답 경우의 수
	 */
	
	static void comb(int depth)
	{
		if(depth==N)
		{
			//System.out.println(Arrays.toString(result));
			//return result;
			dfs(0,0,0,result);
			return;
		}
		
		for(int i=0;i<N;++i)
		{
			if(!visit[i])
			{
				result[depth]=arr[i];	//depth를 인덱스로 써라
				visit[i]=true;
				comb(depth+1);
				visit[i]=false;
			}
		}
		
		
	}
	
	/*
	 * 왼무게, 오른무게, 정답, 깊이, 완성된순열
	 */
	static void dfs(int left, int right, int depth, int arr[])
	{
		
		if(left<right)
		{
			return;
		}
		
		if(depth==N)
		{
			answer++;
			return;
		}
		
		dfs(left+arr[depth],right,depth+1,arr);
		dfs(left,right+arr[depth],depth+1,arr);

	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T= Integer.parseInt(br.readLine());
		
		for(int test=1;test<=T;++test)
		{
			N=Integer.parseInt(br.readLine());
			st=new StringTokenizer(br.readLine());
			arr= new int[N];
			for(int i=0;i<N;++i)
			{
				arr[i]=Integer.parseInt(st.nextToken());
			}
			//입력끝
			
			visit= new boolean[N];
			result=new int[N];
			
			comb(0);
			
			System.out.println("#"+test+" "+answer);
			answer=0;
		}
	}

}