[SWEA] 3234. 준환이의 양팔저울

순열 재귀를 이용하여 푸는 문제이다.

주어진 추를 왼쪽에 놓을때, 오른쪽에 놓을때의 경우를 재귀로 호출하며 풀수있는 문제이다. 다만 여기서 주의할점이 있다. 저울이 양쪽이기에 N개의 추가 있다면 2^N * N!을 총가지수로 가지기 때문에 가지치기가 상당히 중요한 문제이다. 따라서 다음과 같은 가지치기를 하였다. 우선 오른쪽저울에 추가해도 왼쪽저울을 안넘을때 오른쪽 저울에 추가하는 가지치기와 만일 현재왼쪽의 총합*2가 sum을 넘는다면 뒤쪽은 다안보고 한번에 모든 경우를 더해주는 방식으로 가지치기를 하여 시간초과를 통과하였다.

단순한 재귀 문제이지만 가지치기를 하는 방식을 곰곰히 생각해봐야하는 문제이다.

package swea;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution_d4_3234_준환이의양팔저울 {
    
    static int[] numbers;
    static boolean[] visit;
    static int N;
    static int count;
    static int sum;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        
        int T=Integer.parseInt(br.readLine());
        
        for(int tc=1;tc<=T;tc++) {
            N=Integer.parseInt(br.readLine());
            numbers=new int[N];
            visit=new boolean[N];
            sum=0;
            st=new StringTokenizer(br.readLine());
            for(int i=0;i<N;i++) {
                numbers[i]=Integer.parseInt(st.nextToken());
                sum+=numbers[i];
            }
            
            count=0;
            perm(0,0,0);
            System.out.println("#"+tc+" "+count);
            
        }
    
    }
    
    static void perm(int depth,int left, int right) {
        if(depth==N) {
            count+=1;
            return;
        }
        
        if(sum - left <= left) {
            count+=fact(N-depth) *Math.pow(2, N-depth);
            return;
        }
        
        
        for(int i=0;i<N;i++) {
            if(visit[i]==false) {
                visit[i]=true;
                perm(depth+1,left+numbers[i],right);
                visit[i]=false;
                
                if(left >= right+numbers[i]) {
                    visit[i]=true;
                    perm(depth+1,left,right+numbers[i]);
                    visit[i]=false;
                }
                    
            }
        }
        
    }
    
    static int fact(int num) {
        int answer=1;
        for(int i=num;i>=1;i--) {
            answer*=i;
        }
        return answer;
    }
}