[백준] 2317 - 결혼식 (c++)

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

 

문제 요약

N개의 수가 주어진다. K개의 수는 순서를 바꿀수 없고 나머진 바꿀 수 있을 때, 인접한 앞뒤 수의 차이를 모두 더한 값의 최솟값을 구해라.

 

풀이 (N)

• 그리디

순서를 바꿀 수 없는 수들 사이에 바꿀 수 있는 수를 최소가 되게 잘 끼워 넣으면 된다. [l,r] 구간에 속하는 수들에 대해 비용은 r-l이기 때문에 최솟값과 최댓값만 신경쓰면 된다. 순서를 바꿀 수 있는 수들과 바꿀 수 없는 수들의 최솟값과 최댓값을 각각 hmn,hmx,lmn,lmx라고 하자. hmn<lmn일 때와 hmx>lmx일 때 수를 가운데 끼워 넣거나 양 끝에 넣는 경우 중 가장 차이가 적은 것을 고르면 된다. 

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

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,k;cin>>n>>k;
    vector<int> a(k),b(n-k);
    int lmx=0,lmn=1e10;
    for(int& x:a)cin>>x,lmx=max(lmx,x),lmn=min(lmn,x);
    int hmx=0,hmn=1e10;
    for(int& x:b)cin>>x,hmx=max(hmx,x),hmn=min(hmn,x);
    ll ans=0;
    for(int i=1;i<k;i++) 
        ans+=abs(a[i]-a[i-1]);
    if(hmn<lmn)
        ans+=min({abs(hmn-lmn)*2,abs(a[0]-hmn),abs(a[k-1]-hmn)});
    if(hmx>lmx)
        ans+=min({abs(hmx-lmx)*2,abs(a[0]-hmx),abs(a[k-1]-hmx)});
    cout<<ans;
}