BOJ 1469 - 숌 사이 수열

BOJ 1469 - 숌 사이 수열

랭파드 수열을 브루트포스로 찾는 문제이다.

백트랙킹을 이용해 모두 넣어보며 가능한 경우를 모두 모아둔다음 사전순으로 가장 빠른것을 출력해주자.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   vi seat(n * 2, -1);
   vvi cand;
   function<void(int)> fn = [&](int i) -> void {
      if (i == n) {
         cand.pb(seat);
         return;
      }

      int d = a[i];
      for (int j = 0; j + d + 1 < 2 * n; j++) {
         if (seat[j] == -1 && seat[j + d + 1] == -1) {
            seat[j] = seat[j + d + 1] = d;
            fn(i + 1);
            seat[j] = seat[j + d + 1] = -1;
         }
      }
   };
   fn(0);
   sort(all(cand));
   if (!sz(cand))
      cout << -1;
   else for (int k: cand[0]) cout << k << ' ';
}