[C++] 1209 - 단조수열 만들기 (플래티넘4)

1. 문제 설명

 

1209번: 단조수열 만들기

로직은 극단적으로 쉬우나 수학이 문제다..

---

2. 아이디어

 

BOJ 1209 단조수열 만들기 : O(NlgN)

내 처음 아이디어는 이게 아니긴 했지만, 훨씬 깔끔한 코드가 있길래 기억 조작해서 이 코드로 풀었다고 하련다.

얼추 뭐 흐름은 같으니까! 🤪🤪🤪

농담이고 내가 작성한 코드도 다시 다듬어서 시도해보자..대충 문제의 본질은 파악했었는데 왜 안 되는 지 모르겠다.

수학적인 내용은 위 블로그에서 참고하면 된다.

 

우선 순위 큐를 써서 단조 수열을 만들자는 건데 쉬운 내용은 아니다.

참고로 위의 블로그에서는 초기값을 2억으로 잡았는데, 16년도 자료라 그 뒤로 데이터가 추가됐는지

그대로는 통과할 수가 없다.

아무래도 최악의 경우의 수를 고려하면 적어도 200 * 100,000,000 정도로는 초기화해야 한다. 

 

---

3. 코드

#include <iostream>
#include <queue>
#include <algorithm>

#define ll long long
#define endl '\n'

using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int N; cin >> N;
    ll ret = 2001e9;
    ll arr[2010];
    for (int i=0; i<N; i++) cin >> arr[i];

    for (int i=0; i<2; i++) {
        priority_queue<int> q;
        ll tmp = 0;
        for (int j=0; j<N; j++) {
            if (!q.empty() && q.top() > arr[j]) {
                tmp += q.top() - arr[j];
                q.pop();
                q.push(arr[j]);
            }
            q.push(arr[j]);
        }
        ret = min(ret, tmp);
        reverse(arr, arr+N);
    }
    cout << ret << endl;
    return 0;
}