핵심 아이디어

<aside> 💡

$1\le i<j \le n$인 $i, j$에 대해 $a_i>a_j$라면 $a_j$는 반드시 한 번은 이동이 필요하다.

이러한 $a_j$들을 모아 큰 것부터 꺼내서 맨 위에 넣으면 이동 횟수가 최소화 된다.

이때 $a_j$들을 맨 위로 보낸 후 기존에 정렬되어 있던 볼링공들 중 $a_j$들 중 최대값보다 작은 볼링공들은 또 다시 정렬이 필요하다.

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long int ll;

int n;

signed main()
{
    FASTIO;
    vector<int> a;
    int w;

    cin >> n;
    cin >> w;
    a.push_back(w);
    int ans = 0;
    int mx = 0;
    for(int i = 1; i<n; i++){
        cin >> w;
        if(a.back() > w){
            ans++;
            mx = max(mx, w);
        }
        else{
            a.push_back(w);
        }
    }
    
    cout << ans + (lower_bound(a.begin(), a.end(), mx)-a.begin());
    return 0;
}

무려 내가 1등이다!