[백준/BOJ] 13146 같은 수로 만들기 2

문제 : 13146 같은 수로 만들기 2

13146번: 같은 수로 만들기 2

단순하게 생각했을때 배열이 오름차순 or 내림차순으로 정렬되어 있다면

abs(arr[0]-arr[N-1])번만 add()연산을 실행해주면 된다.

 

따라서 배열에 수가 들어올 때 마다 배열을 내림차순 수열로 만들어준다고 생각하면

현재 들어온 M번째 수가 이전보다 작은수라면 냅두고

큰수라면 현재까지 저장된 수열들을 M번째 수와 같게 만들어주면 다시 내림차순 수열로 저장할 수 있다.

이때 같게 만들기 위해서는 이미 앞부분이 내림차순 수열이므로 arr[M]-arr[M-1]번만 add()연산을 해주면 된다. 

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, ans;
deque<ll> dq;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    while (N--){
        ll x;
        cin >> x;
        if (!dq.empty() && dq.back()<x){ // 내림차순이 아니라면
            ll y=dq.back();
            ans+=x-y; // 차이나는만큼 더하는 행동 실행
            while (!dq.empty() && dq.back()<x) // 다 같아졌으므로 앞의 원소들 제거하기
                dq.pop_back();
        }
        dq.push_back(x);
    }
    cout << ans+dq.front()-dq.back(); // 지금까지 증가시킨 횟수 + 내림차순일때 횟수
    return 0;
}