백준 12237, Up and Down (Large)

개요

문제 링크
골드 5, Greedy, DP
팰린드롬을 만들기 위한 최소 swap 수

---

접근

1. 처음에 upper bound를 이용해서 왼쪽부터 오름차순, 오른쪽부터 내림차순으로 정렬하면서 left_swap + right_swap의 최솟값을 구했는데 실패.
2. 머리가 나빠서 다른 풀이는 생각 안남. 그냥 codejam 검색해서 analysis를 보고 이해했음. Greedy랑 DP가 섞이면 골5도 못푸는 멍청이라 너무 슬프다..
3. DP보다는 그리디가 더 중요했던 문제, 방법은 최솟값을 선택하고, 왼쪽과 오른쪽 중 더 가까운 swap 수를 더하고, 최솟값을 지워주면 되는 데 이게 왜 되냐? 아래 예시를 보자.

875691243 -> 87569243(1) -> 8756943(21) -> 8756943(21) -> 875694(321)
-> 87569(4321) -> (5)8769(4321) -> (5)879(64321) -> (57)89(64321)
-> (5789)(64321)

알아서 최소의 swap을 통해 팰린드롬 정렬이 됐다. 왼쪽과 오른쪽 덩어리는 알아서 오름차순/내림차순으로 정렬되고 이게 최적임.
다시보니까 코드포스 Forbidden permutation과도 닮아 있다.

---

Pseudo code

while (n--)
    i = get_min_index()
    swap += min(i, n-i)
    remove(i)

---

Source code

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

vector <int> a;
int get() {
    int m = 2e9, ans;
    for (int i=0; i<a.size(); i++) {
        if (a[i] < m)
            ans = i, m = a[i];
    }
    return ans;
}

int test() {
    int n;
    cin >> n;
    a.clear();
    int x;
    for (int i=0; i<n; i++)
        cin >> x, a.push_back(x);
    int ans = 0;
    while (n--) {
        int i = get();
        ans += min(i, n-i);
        a.erase(next(a.begin(),i));
    }
    return ans;
}

int main() {
    int t;
    cin >> t;
    for (int i=1; i<=t; i++)
        printf("Case #%d: %d\n",i,test());
}