[SWEA] 3234. 준환이의 양팔저울(d4) ★★☆

문제

준환이는 N개의 서로 다른 무게를 가진 무게 추와 양팔저울을 가지고 있다.

모든 무게 추를 양팔저울 위에 올리는 순서는 총 N!가지가 있고,

여기에 더해서 각 추를 양팔저울의 왼쪽에 올릴 것인지 오른쪽에 올릴 것인지를 정해야 해서 총 2^N * N!가지의 경우가 있다.

하지만 양팔 저울에 갑자기 문제가 생겨서 무게 추를 올릴 때 오른쪽 위에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 커져서는 안 된다.

예를 들어 무게추가 총 3개, 무게가 각각 1, 2, 4 라고 하면 아래 그림처럼 총 15가지 경우가 나올 수 있다.

이런 방법으로 준환이가 양팔 저울에 모든 무게추를 올리는 방법은 총 몇 가지가 있을까?

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다 첫 번째 줄에 N(1 ≤ N ≤ 9)가 주어진다.

두 번째 줄에는 각 무게추의 무게를 의미하는 N개의 자연수가 공백으로 구분되어 주어진다. 무게는 1이상 999이하이다.

[출력]

각 테스트 케이스마다 무게추를 올리는 과정에서 오른쪽 위에 올라가있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 커지지 않는 경우의 수를 출력한다.

입력

3
3
1 2 4
3
1 2 3
9
1 2 3 5 6 4 7 8 9

출력

#1 15
#2 17
#3 35583723

풀이

문제 유형 : 순열, 부분집합, 백트래킹
1. 추를 놓을 순서를 먼저 구한다. (순열)
2. 순열을 찾았다면, 순서대로 추를 왼쪽에 놓을 경우와 오른쪽에 놓을 경우로 구분하는데, 오른쪽에 놓을 때는 왼쪽에 놓인 추의 무게의 합보다 작거나 같을 때에만 놓는다. (부분집합, 백트랙킹)

---

① 번 코드가 ② 번 코드보다 훨씬 빨랐다.
아마도 순열을 구하면서 현재 추를 왼쪽에 놓을지 오른쪽에 놓을 지 결정하면 더 많은 가지가 불리는 것 같다.

코드

① 순열을 구한 후 부분집합 (더 빠름)

import java.io.*;
import java.util.*;

public class Solution {

	static int ans;
	static int[] chu, select;
	static boolean[] visited;
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("res/input_d4_3234.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			int n = Integer.parseInt(br.readLine());
			
			chu = new int[n];
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<n; i++) {
				chu[i] = Integer.parseInt(st.nextToken());
			}
			
			visited = new boolean[n];
			select = new int[n];
			ans=0;
			perm(0, n);
			
			sb.append("#").append(tc).append(" ").append(ans).append("\n");
		}
		
		System.out.print(sb.toString());
		br.close();
	}
	
	static void perm(int cnt, int n) {
		if(cnt==n) {
			choice(0, n, 0, 0);
			return;
		}
		
		for(int i=0; i<n; i++) {
			if(visited[i]) continue;
			visited[i] = true;
			select[cnt] = chu[i];
			perm(cnt+1, n);
			visited[i] = false;
		}
	}
	
	static void choice(int idx, int n, int left, int right) {
		if(idx == n) {
			ans++;
			return;
		}
		
		choice(idx+1, n, left+select[idx], right);
		if(right+select[idx] <= left) choice(idx+1, n, left, right+select[idx]);
	}
	
}

② 순열을 찾으면서 부분집합 (더 느림)

import java.io.*;
import java.util.*;

public class Solution {

	static int ans;
	static boolean[] visited;
	static int[] chu;
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("res/input_d4_3234.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			int n = Integer.parseInt(br.readLine());
			
			chu = new int[n];
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<n; i++) {
				chu[i] = Integer.parseInt(st.nextToken());
			}
			
			ans = 0;
			visited = new boolean[n];
			perm(0, n, 0, 0);
			
			sb.append("#").append(tc).append(" ").append(ans).append("\n");
		}
		
		System.out.print(sb.toString());
		br.close();
	}
	
	static void perm(int cnt, int n, int left, int right) {
		if(cnt==n) {
			ans++;
			return;
		}
		
		for(int i=0; i<n; i++) {
			if(visited[i]) continue;
			visited[i] = true;
			perm(cnt+1, n, left+chu[i], right);
			if(right+chu[i] <= left) perm(cnt+1, n, left, right+chu[i]);
			visited[i] = false;
		}
		
	}
	
}