[SWEA] SWEA3234_준형이의 양팔저울_백트래킹

순열과 부분집합을 동시에 적용해야 풀 수 있는 문제이다. 코드를 보면 파바박 할 수 있을 것 같지만, 백지상태에선 막막했다.

게다가 백트래킹(가지치기)를 제대로 하지 않으면 시간초과까지 뜨니 효율성도 고려해야 한다.

 

결론적으로 순열+부분집합+백트래킹을 연습할 수 있는 good 문제.

 

문제.

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

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

여기에 더해서 각 추를 양팔저울의 왼쪽에 올릴 것인지 오른쪽에 올릴 것인지를 정해야 해서 총 2N * 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

//testCase의 개수 //N = 3 //각 무게추 무게 1, 2, 4

[출력]

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

 

#1 15
#2 17
#3 35583723//TestCase 1의 답

 

 

풀이

무게 1 2 4가 있다면 

1 2 4

1 4 2

2 1 4

2 4 1

...이렇게 순서를 고려해서 3개를 뽑아야 하므로 permutation이다.

 

근데 하나를 뽑을때마다 왼손오른손이 달라진다.

같은 순서 1 2 4에서도

1(왼) 2(왼) 4(왼)

1(왼) 2(왼) 4(오)

1(왼) 2(오) 4(왼)

....1(오) 2(오) 4(오) 이렇게 3개에서만 해도 경우의 수가 벌써 2^3개나 된다.

 

전략:

1. 일단 n개를 뽑는 permutation을 돌린다.

2. 단!! permutation의 인자에 왼손의 합, 오른손의 합을 같이 딸려보낸다.

3-1 재귀가 도는 중간중간 왼손 오른손의 합이 조건을 벗어나면 return시킨다.

3-2 재귀가 도는 중간중간 더이상 남은 무게들을 다 오른손에다가 줘도 왼손을 넘을 수 없는 경우엔 더이상 진행시키지 않고 남은 모든 경우의 수를 답에다가 추가해준다. 이건 남은 무게의 수가 n개라면, n! * 2^n이 된다. (문제에도 나와있음)

 

위 전략에서 2번을 떠올리면 50퍼센트 성공이다. 그리고 시간초과가 날것이다.

그 때 3-2를 떠올리면 해결이 된다.

 

위 전략방법들을 모두 구현했는데도 시간초과가 떴었다...그래서 ㄱ고생했는데 원인은 33번째 줄에서 sum을 0으로 초기화해주지 않았던 것이다. 그래서 테스트케이스가 여러개 주어질 때 3-2방법에서 가지치기가 실행되지 않아 시간초과가 발생한 것이다..ㅠㅠㅠ 

 

다음은 코드.

package ws0218;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
1
9
1 2 3 5 6 4 7 8 9
 */
public class SWEA3234_준환이의양팔저울_백트래킹 {
	static int[] weights;
	static boolean[] selected;
	static int N;
	static int sum;
	static int[] factorial = new int[10];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;
		factorial[1] = 1;
		for(int i=2; i<10; i++) {
			factorial[i] = i*factorial[i-1];
		}
		
		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());//추의 개수
			selected = new boolean[N];
			weights = new int[N];
			st = new StringTokenizer(br.readLine());
			sum = 0;
			for(int i=0; i<N; i++) {
				weights[i] = Integer.parseInt(st.nextToken());
				sum+=weights[i];
			}
			
			pick(0,0,0);
			int ans2 = ans;
			ans =0;
			sb.append("#").append(tc).append(" ").append(ans2).append("\n");
		}
		System.out.print(sb.toString());
	}

	static int ans=0;
	static void pick(int cnt, int left, int right) {

		if(cnt == N) {
			ans++;
			return;
		}
		int remain = sum - left -right;
		if(left >= remain+right) {
			ans+= factorial[N-cnt]*(1<<N-cnt);
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(selected[i] == false) {
				selected[i] = true;
				pick(cnt+1, left+weights[i], right);
				
				
				if(left>=right+weights[i]) {
					pick(cnt+1,left, right+weights[i]);
				}
				
				selected[i] = false;
			}			
 		}
	}
	
}