백준[22965] k개의 부분 배열

문제 풀이

문제 링크

http://icpc.me/22965

22965번: k개의 부분 배열

풀이

이 문제는 아이디어만 잘 생각해낸다면 쉽게 풀 수 있는 문제다. 처음에 삽질을 좀 많이 했는데 푸는데 매우 재밌었다.

잘 생각을 해보면 이 문제에서 나올 수 있는 k의 값의 최댓값은 3이다.

이유는 간단하다. 선택 정렬을 하듯이 가장 큰 값, 또는 가장 작은 값을 찾아서 그 수를 맨 앞, 또는 맨 뒤로 보내는 과정을 계속하면 정렬이 될 것이다. 

예를 들어, 4 3 6 1 2 5 로 수행을 해보자.

4 3 6 | 1 | 2 5 -> 4 3 6 2 5 1

4 3 6 | 2 | 5 1 -> 4 3 6 5 1 2

4 | 3 | 6 5 1 2 -> 4 6 5 1 2 3

4 | 6  5 | 1 2 3 -> 6 5 1 2 3 4

6 | 5 | 1 2 3 4 -> 1 2 3 4 5 6

k = 2일 때는 당연히 모든 수가 정렬되어 있을 때이고, 이제 언제 k를 2로 만들 수 있는지만 생각하면 된다.

배열의 수를 정렬된 두 그룹으로 나눌 수 있고, 왼쪽에 있는 배열의 최솟값보다, 오른쪽에 있는 배열의 최댓값이 더 커야 한다.

코드

#include <cstdio>

int arr[200005];

int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", arr + i);
    int ans = 1, cnt = 0, m = 1e9;
    arr[0] = -1e9;
    bool sorted = true, flag = true;
    for (int i = 1; i <= n; i++) {
        if (arr[i] < arr[i - 1]) {
            sorted = false;
            cnt++;
        }
        if (cnt && arr[i] > arr[1]) flag = false;
    }
    if (sorted) printf("1");
    else if (cnt == 1 && flag) printf("2");
    else printf("3");
}