BOJ 24337 - 가희와 탑

BOJ 24337 - 가희와 탑

심상치 않은 정답률의 문제

Greedy + Constructive 문제이다.

최대한 빠르게 증가시킬 때 1 2 3 4 5 ... 처럼 되어야 하므로 $a$를 만들기 위해 최소 앞에서부터 $a$ 칸이 필요하고

$b$를 만들기위해 최소 뒤에서부터 $b$칸이 필요하다.

이것이 만족되지 못하면 $-1$을 출력한다.

$a=1$ 일 때는 특별하게 처리해줘야 하니까 잠시 뒤에 보고,

$a > 1$ 이라 하자.

그럼 뒤에서부터 $b$ 번째 칸에 무조건 $h=Max(a,b)$ 를 채워준다.

이후 뒤로는 만약 $b \ge a$ 라면 $h, h-1, h-2, \dots, 1$ 처럼 될 것이다.

$b<a$ 라면 $h=a$ 이고 $h,b-1, b-2, \dots, 1$ 처럼 된다.

앞부분도 마찬가지로 채워준다.

1 1 1 1 1 2 3 4 ..a-1 h b-1.. 1 처럼 되는게 항상 최적이란 것을 알 수 있다.

$a=1$ 이라 하자.

그럼 $b$를 첫 칸에 채워버리고 뒤 부분은 b-1 b-2 ... 1 1 1 1 처럼 되는게 최적이다.

void solve() {
   int n, a, b;
   cin >> n >> a >> b;
   int h = max(a, b), hl = a - 1, hr = n - b;
   vi ans(n + 1, -1);
   if (hl > hr) {
      cout << -1;
   } else if (a == 1) {
      ans[0] = h;
      ans[n - b + 1] = h - 1;
      for (int i = n - b + 2; i < n; i++) ans[i] = ans[i - 1] - 1;
      for (int i = 0; i < n; i++) cout << max(1, ans[i]) << ' ';
   } else {
      int pivot = a == 1 ? 0 : hr;
      ans[pivot] = h;
      ans[pivot + 1] = b - 1;
      for (int i = pivot + 2; i < n; i++) ans[i] = ans[i - 1] - 1;
      ans[pivot - 1] = a - 1;
      for (int i = pivot - 2; i >= 0; i--) ans[i] = ans[i + 1] - 1;
      for (int i = 0; i < n; i++) cout << max(1, ans[i]) << ' ';
   }
}