백준 17074, 정렬

개요

문제 링크
실버 1, DP
배열에서 한 원소를 삭제했을 때 배열이 비내림차순인 경우의 수

---

접근

1. 하나를 삭제하는 것이므로 어떤 전처리를 하고 O(n)을 돌면서 확인해준다.
2. 조건을 생각한다. 제거 후 비내림차순이려면 왼쪽과 오른쪽이 비내림차순이면 된다.
3. i에 대해 b[i]는 1~i까지 비내림차순 여부, c[i]는 i~n까지 비내림차순 여부를 저장한다.
4. b[i-1] && c[i+1]이면 count 증가, 단 왼쪽 원소가 오른쪽 원소보다 작아야 함.

---

Pseudo code

b[i] = (1~i) left_ascending_order
c[i] = (i~n) right_ascending order
if (b[i-1] && c[i+1] && a[i-1] <= a[i+1])
    count++;

---

Source code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n+2];
    a[0] = -2e9;
    a[n+1] = 2e9;
    for (int i=1; i<=n; i++)
        cin >> a[i];
    int b[n+2], c[n+2];

    b[0] = 1, c[n+1] = 1;
    int v = 1;
    for (int i=1; i<=n; i++) {
        if (a[i] < a[i-1])
            v = 0;
        b[i] = v;
    }
    v = 1;
    for (int i=n; i>=1; i--) {
        if (a[i+1] < a[i])
            v = 0;
        c[i] = v;
    }
    int ans = 0;
    for (int i=1; i<=n; i++)
        if (b[i-1] && c[i+1] && a[i-1] <= a[i+1])
            ans++;
    cout << ans;
}