SWEA-3234 준환이의 양팔저울

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

SW Expert Academy

---

순열 + Powerset문제

***주의할 점***

static 변수 참조에 의한 시간 초과를 조심해야하는 문제. 

추 배열을 재귀함수의 인자로 넘겨주어야 함.

---

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int N,res;
	public static void main(String[] args) throws FileNotFoundException {
		//permutation을 넘겨줘야함. 인자(방문배열, idx, left무게,right무게)
		System.setIn(new FileInputStream("input/준환이의양팔저울.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			
			N =sc.nextInt();//추의 개수
			int arr[] = new int[N];//추 배열
			res=0;//경우의 수 count
			for (int i = 0; i < N; i++) {
				arr[i]=sc.nextInt();
			}
			perm(arr,new boolean[N],0,0,0);//재귀 시작
		
			System.out.printf("#%d %d\n",tc, res);
		}
		
	}
	/*
	 * 순열 + 파워셋.
	 *담을필요없고 오른쪽, 왼쪽 "값" 만 갖고있으면된다 ->int 선언해줌
	 *static을 쓰면 좀더느리다. 지역변수쓰기.
	 */
	private static void perm(int arr[],boolean v[],int k, int left, int right) {
		if(left < right)return;//오른쪽 합이 왼쪽보다 더 큰경우 return ->가지치기
		
		if(k==arr.length) {
			res++;
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if(v[i]) continue;
			v[i]=true;
            /*
            * 부분집합의 개념 : 뽑고, 뽑지않고
            */
			perm(arr, v,k+1, left, right+arr[i]);//오른쪽에 추가하는 경우
			perm(arr, v,k+1, left+arr[i], right);//왼쪽에 추가하는 경우
			v[i]=false;
		}
		
	}
}