SWEA 3234 - 준환이의 양팔저울

Java

3234 번 - 준환이의 양팔저울

문제

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

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

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

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

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

접근 방법

문제를 이해하는데 상당히 어려웠으며 몇 번이나 잘못 이해하여 쌩뚱맞은 코드를 구현하고 있었다.
문제를 다시 풀어서 이해하면,

n개의 추를 앞에서 부터 하나씩 뽑아서 양팔 저울에 올린다.  
뽑은 추를 왼쪽 혹은 오른쪽에 올리게 하는데, 올리는 도중에 왼쪽보다 오른쪽 추들의 무게가 더 나가, 오른쪽으로 기울어지면 안된다.  
즉, n개의 추를 양팔 저울에 순서대로 올리는데, 오른쪽으로 기울어지면 안된다.  

DFS를 이용한 순열을 구하여 n개의 추를 저울에 하나씩 올린다.
여기서 중요한 점이, 선택한 추 하나를 왼쪽 저울에 올리는 경우와 오른쪽 저울에 올리는 경우 2가지를 선택하여 새로운 DFS에 들어간다.
문제 조건에서 왼쪽 추의 총 합이 오른쪽 추의 총 합보다 커야하므로, 오른쪽 추를 올릴 때 현재까지 올린 왼쪽 추의 무게보다 작아야지 올리는 DFS를 호출한다.

코드

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

class Solution {
	static int result = 0;
	static int cnt = 0;

	public static void main(String []args) throws Exception {  
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	int tc = stoi(br.readLine());
    	
    	for(int tidx = 1; tidx <= tc; tidx++) {
    		int n = stoi(br.readLine());
    		result = 0;
    		int[] arr = new int[n];
    		boolean[] vis = new boolean[n];

    		st = new StringTokenizer(br.readLine());
    		for(int i = 0; i < n; i++) {
    			arr[i] = stoi(st.nextToken());
    		}
    		DFS(0, 0, 0, arr, vis, n);
    		
    		System.out.println("#" + tidx + " " + result);
    	}
    	
	}
	
	static void DFS(int lv, int l, int r, int[] arr, boolean[] vis, int n) {
		// n개 까지 뽑았다는 것은 중간에 멈추지 않고 다 뽑았다는 것이므로 결과 cnt + 1
		if(lv == n) {
			result++;
			return;
		}
		for(int i = 0; i < n; i++) {
			if(!vis[i]) {
				vis[i] = true;
				
				// 왼쪽만 일단 올리는 경우. 왼쪽 순서대로 올리면, 무조건 오른쪽 보다는 크므로 가능
				DFS(lv + 1, l + arr[i] , r, arr, vis, n);
				// 오른쪽 저울에 올린 경우, 현재까지의 왼쪽 보다 작으면 오른쪽에 올릴 수 있다.
				if(r + arr[i] <= l) {
					// 오른쪽에도 하나 올린다
					DFS(lv + 1, l , r + arr[i], arr, vis, n);
				}
				vis[i] = false;
			}
		}
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐⭐⭐⭐

후기

우선 문제 이해부터 2번이나 잘못하여, 시간을 많이 날렸다.
게다가 문제 이해를 제대로 했어도 구현을 하는데, n개의 추를 먼저 뽑아놓고 이후에 추를 왼쪽으로 올릴지, 오른쪽으로 올릴지 고민하고 있었다.
가지 치기로 Back Tracking 문제였지만, 나의 부족으로 단순히 순열을 통해 뽑아 놓은 이후, 결과를 계산하는 방식으로만 사로잡혀 있던 것을 깨주는 문제였다.
N개의 추를 순열로 뽑는 DFS + 각 추를 왼쪽 or 오른쪽에 놔두는 경우인 부분집합을 합한 문제인 것 같다.

즉, n개의 값을 뽑고, 각 값을 n칸의 공간에 하나씩 넣을 때는(각 공간에는 1~m 경우의 수가 있다. 이 문제는 2)
DFS를 통해 구현하되 sel 선택과 새로운 DFS 호출을, [왼쪽, 오른쪽] 구분하여 새롭게 DFS를 호출하는 방식으로 해결하면 된다.

개선할 점

많다. 스스로 부족함을 깨닫게 해준 문제다.