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

1. 문제

SW Expert Academy

무게 추를 올릴 때 오른쪽 위에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 커져서는 안 된다.

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

---

2. 풀이

왼쪽 저울에 올라갈 순열을 찾는다.

cnt==N이면 다 찾은 경우이므로 result에 1을 더한다.

경우의 수를 찾다가 중간에 이미 left가 나머지+right보다 더 크면 그 뒤의 경우의 수((N-cnt)! * 2^(N-cnt))를 전부 더해주고 끝낸다.

0부터 N-1 중에 이미 뽑은 추는 제외하고 나머지를 오른쪽, 왼쪽으로 저울에 올린다. (재귀호출)

오른쪽으로 올릴 때는 left보다 right+현재 추 무게가 같거나 작을 때만 가능하다.

import java.io.*;
import java.util.*;
 
public class D4_3234_준환이의양팔저울 {
   private static int N, result;
   private static int[] weights;
 
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;
      StringBuilder sb = new StringBuilder();
 
      int T = Integer.parseInt(in.readLine());
 
      for (int tc = 1; tc <= T; tc++) {
         sb.append("#").append(tc).append(" ");
         result = 0;
         int total = 0;
 
         N = Integer.parseInt(in.readLine());
         weights = new int[N];
 
         st = new StringTokenizer(in.readLine());
         for (int i = 0; i < N; i++) {
            weights[i] = Integer.parseInt(st.nextToken());
            total += weights[i];
         }
 
         measure(0, 0, 0, total, 0);
 
         sb.append(result).append("\n");
      }
 
      System.out.print(sb);
   }
 
   private static void measure(int cnt, int left, int right, int stock, int flag) {
      int[] pow = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
      int[] factorial = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
 
      if (cnt == N) {
         ++result;
         return;
      }
 
      if (left >= stock + right) {
         result += factorial[N - cnt] * pow[N - cnt];
         return;
      }
 
      for (int i = 0; i < N; i++) {
         if ((flag & 1 << i) != 0) continue;
         measure(cnt + 1, left + weights[i], right, stock - weights[i], flag | 1 << i);
         if (left >= right + weights[i]) {
            measure(cnt + 1, left, right + weights[i], stock - weights[i], flag | 1 << i);
         }
      }
   }
}

---

3. 결과

시간초과가 너무너무 많이 났던 문제였다. 

그래서 2의 n제곱을 미리 만들어 놓기도 하고, 팩토리얼도 9!까지 만들어놨다. 그런데도 시간초과가 났다.

가지치기도 잘 한 것 같은데 계속 틀려서 찾아보니 total이 문제였다. total을 static변수로 설정하고 (left >= total-left) 비교했었는데 함수 내에 있는 매개변수 접근보다 전역변수 접근이 더 느려서 그랬나보다. 원거리 변수보다 근거리 변수 접근이 더 빠른 것이 당연하기는 하다.