BOJ 1653 - 양팔 저울

BOJ 1653 - 양팔 저울

$10!$ 을 이용해 브루트포스도 가능한 모양이지만 나는 dp로 해결했다.

그랬더니 1등이 되었다?

$dp$의 정의는 다음과 같다.

$dp[i][used][q]$= 현재 인덱스가 $i$ 이고 $n$개의 숫자 중 사용된 것이 $used$ 개이고 현재 저울의 왼쪽에 있다면 $(i \le 4)$ 지금까지 왼쪽의 무게의 합은 $q$ 이고 오른쪽에 있다면 $(i \ge 5)$ 평형을 맞추기 위해 더 두어야 할 무게의 합이다.

이걸 이용하면 $O(10 \cdot 2^9 \cdot 150 \cdot n)$ 정도로 문제를 풀 수 있고 역추적은 그것보다 빠르므로 문제를 빠르게 해결할 수 있다.

int n, k;  
vi a;  
int dp[10][1 << 9][150];  
  
int fn(int i, int used, int q) {  
   if (q < 0) return 0;  
   // 모든 위치를 다 봤을 때는 평형이 맞아야 1개로 쳐준다.  
   if (i == 10) return q == 0;  
   // DP  
   int &ret = dp[i][used][q];  
   if (~ret) return ret;  
   ret = 0;  
  
   bool is_left = i <= 4;  
   int multiple = abs(i - 5) + !is_left;  
  
   // 1. 그냥 넘기기  
   ret += fn(i + 1, used, q);  
  
   for (int j = 0; j < n; j++) {  
      // 이미 사용했으면 못쓴다.  
      if (used & (1 << j)) continue;  
  
      if (is_left) {  
         ret += fn(i + 1, used | (1 << j), q + multiple * a[j]);  
      } else {  
         ret += fn(i + 1, used | (1 << j), q - multiple * a[j]);  
      }  
   }  
   return ret;  
}  
int ans;  
void track(int i, int used, int q) {  
   if (i == 10) {  
      cout << ans;  
      exit(0);  
   }  
   int cnt = fn(i + 1, used, q);  
   if (cnt <= k) {  
      k -= cnt;  
   } else {  
      ans *= 10;  
      track(i + 1, used, q);  
      return;  
   }  
  
   bool is_left = i <= 4;  
   int multiple = abs(i - 5) + !is_left;  
  
   for (int j = 0; j < n; j++) {  
      // 이미 사용했으면 못쓴다.  
      if (used & (1 << j)) continue;  
  
      if (is_left) {  
  
         cnt = fn(i + 1, used | (1 << j), q + multiple * a[j]);  
         if (cnt <= k) {  
            k -= cnt;  
         } else {  
            ans = ans * 10 + a[j];  
            track(i + 1, used | (1 << j), q + multiple * a[j]);  
            return;  
         }  
      } else {  
         cnt = fn(i + 1, used | (1 << j), q - multiple * a[j]);  
         if (cnt <= k) {  
            k -= cnt;  
         } else {  
            ans = ans * 10 + a[j];  
            track(i + 1, used | (1 << j), q - multiple * a[j]);  
            return;  
         }  
      }  
   }  
  
   // k가 없는 경우  
  
  
}  
  
void solve() {  
   memset(dp, -1, sizeof dp);  
   cin >> n;  
   a.resize(n);  
   fv(a);  
   cin >> k;  
   int total_cnt = fn(0, 0, 0);  
   k = min(total_cnt - 1, k);  
   track(0, 0, 0);  
}