BOJ 24337 - 가희와 탑

image.png

심상치 않은 정답률의 문제

Greedy + Constructive 문제이다.

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

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

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

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

a>1a > 1 이라 하자.

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

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

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

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

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

a=1a=1 이라 하자.

그럼 bb를 첫 칸에 채워버리고 뒤 부분은 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]) << ' ';
   }
}

Tags:

Categories:

Updated:

Comments

You may also enjoy