[백준] 2322 - 아령, 2569 - 짐정리 (c++)

https://www.acmicpc.net/problem/2322

https://www.acmicpc.net/problem/2569

 

문제 요약

N개의 물건이 있고 각각 무게가 주어진다. 두 물건의 위치를 바꿀수 있고 두 무게의 합만큼의 힘이 들 때 최소 힘으로 물건을 무게순으로 정렬해라.

 

풀이 (NlogN)

• 순열 사이클 분할
• 그리디

오름차순으로 정렬 했을 때 자리가 바뀌는 수는 모두 사이클에 속하게 된다. 사이클엔 오름차순을 했을 때에 각 순서의 숫자가 모두 포함되어 있기 때문에 각각에 사이클에서 오름차순을 해준다면 전체도 오름차순이 된다. 사이클 안에서 정렬하는 비용은 사이클 안에 가장 작은 원소를 이용하는 방법(cymin*(cnt-2)+sum) 전체에서 가장 작은 원소를 사이클 내 가장 작은 원소와 바꿨다가 돌려놓는 방법(min*(cnt+1)+sum+cymin) 중 작은 것이 최소이다.

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

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;cin>>n;
    array<ll,2> g[n];
    int i=0;
    for(auto& [a,b]:g) cin>>a,b=i++;
    sort(g,g+n);
    bool vis[n]{};ll ans=0;
    for(int i=0;i<n;i++) {
        if(vis[i]) continue;
        int cnt=0;
        for(int j=i;!vis[j];j=g[j][1])
            vis[j]=1,cnt++,ans+=g[j][0];
        ans+=min(g[0][0]*(cnt+1)+g[i][0],g[i][0]*(cnt-2));
    }
    cout<< ans;
}

 

감상

순열 사이클 분할로 이런 문제를 해결할 수 있다는게 정말 신기했다.