BOJ 22965 - k개의 부분 배열

BOJ 22965 - k개의 부분 배열

정답은 최대 $3$개임을 관찰한다.

정렬이 되어있다면 $1$이고, $k, k + 1,k + 2 \cdots, 1, 2, 3, \cdots, k-1$ 처럼 정렬이 되어있다면 $2$ 이다.

그 이외의 경우엔 항상 $k=3$ 으로 움직일 수 있다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   vi b = a;
   sort(all(b));
   if (a == b) {
      cout << 1;
      return;
   }
   uniq(b);
   for (int &i: a) i = lbi(b, i);
   int s = 0;
   for (int i = 0; i < n; i++) if (a[i] == 0) s = i;
   bool can2 = 1;
   for (int i = s + 1; i < n; i++) {
      if (a[i] != a[i - 1] + 1)can2 = 0;
   }
   for (int i = 1; i < s; i++) {
      if (a[i - 1] + 1 != a[i]) can2 = 0;
   }
   if (can2) {
      cout << 2;
   } else cout << 3;
}