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

SW Expert Academy

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

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

DFS를 이용하여 순열을 구현하는 문제다.

나는 올리는 과정에서도 오른쪽이 왼쪽보다 무게가 적어야 한다는 것을 생각하지 못해서 2번정도 fail했다.

DP를 이용하지 않고 순열로 구현했기 때문에, StringBuilder와 매개 변수로 전달해주어야 시간 초과가 나지 않는다.

 

풀이 방법

1. dfs를 이용해서 순열을 구현한다.

2. 아래 두가지 경우로 재귀 호출을 한다.

   2-1. 왼쪽에 추를 올리는 경우

   2-2. 오른쪽에 올려도 왼쪽이 무거운 경우

3. 올린 추가 N개 일때 왼쪽과 오른쪽의 무게를 비교해준다.

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

public class Solution {

	public static int ans;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			int N = Integer.parseInt(br.readLine());;
			int[] weight = new int[N];
			boolean[] v = new boolean[N];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				weight[i] = Integer.parseInt(st.nextToken());
			}
			ans = 0;
			dfs(N, 0, 0, 0, weight, v);
			sb.append("#").append(tc).append(" ").append(ans).append("\n");
		}
		System.out.println(sb.toString());
		
	}
	public static void dfs(int N, int cnt, int right, int left, int[] weight, boolean[] v) {
		if (cnt == N) {
			if (right <= left) {
				ans++;
			}
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if (!v[i]) {
				v[i] = true;
				dfs(N, cnt + 1, right, left+weight[i], weight, v);
                if (left >= right + weight[i])
                	dfs(N, cnt + 1, right + weight[i], left, weight, v);
				v[i] = false;
			}
		}
	}
}