Boj 2984 c++

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

 

문제

 

나들목에서 고속도로로 나가는 경우에 티켓을 발급 받는다. 이후, 다시 고속도로에서 나들목으로 들어가는 경우에는

들어가는 지점과 티켓을 발급받은 지점의 차 만큼 통행료를 지급한다. N명의 사람들이 있을 때, N명의 사람들이 서로 티켓을 바꾸었을 때의 최소 비용의 합을 구하여라.

 

(단, 나가는 위치와 다시 들어오는 위치가 같을 수는 없으며, 모든 사람들의 들어오는 위치와 나가는 위치는 겹치지 않는다.)

 

 

 

접근 & 풀이

 

에디토리얼을 참고하여 풀이하였다.  https://hsin.hr/coci/archive/2007_2008/

Croatian Open Competition in Informatics 2007/2008

 

 

길이가 같은 두 수열이 주어졌을 때 두 수열의 각 원소의 차의 총합을 최소화하는 방법은 두 수열을 정렬한 후, 

하나씩 매칭하는 것이다.

 

하지만 이 문제에서는 매칭 되는 두 수가 같은 경우를 금지하고 있다. 때문에, 최적의 경우는 양 옆의 원소와 교차하여 매칭하는 것이다. 왼쪽, 또는 오른쪽으로 매칭할 수 있으므로 새롭게 섞이는 구간은 최대 길이가 3이다.

 

즉, 들어오는 지점과 나가는 지점을 각각 정렬한 후 하나씩 매칭하되, 길이가 1 ~ 3인 구간을 섞는 경우를 포함하여 매칭되는 두 수가 같은 경우를 제외한다.

 

이때, 매칭된 두 수가 같은 경우에 대해서는 아주 큰 수를 반환하여 이후 dp 값에 전이되지 않게 하면 된다.

(불가능한 경우를 제외하는 것보다 무시해주는 것이 더 쉽다)

 

 

배열의 순서를 달리하여 매칭하는 부분에서는 next_permutation 이라는 기능을 사용하면 유용하니 알아두자.

 

 

 

 

정답코드

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

ll dp[100001];
int perm[3];

ll calc (ll a, ll b) {
    if(a == b)return inf;
    return abs(a-b);
}

int main() {

    int N; cin >> N;
    
    vector<ll> a(N), b(N);

    for(int i = 0; i <= N; i++)
        dp[i] = inf;

    for(int i = 0; i < N; i++) {
        cin >> a[i] >> b[i]; // 들어올 때 나갈 때
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    dp[0] = 0;

    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= 3 && i - j >= 0; j++) {
            for(int k = 0; k < j; k++) {
                perm[k] = k;
            }
            do {
                ll cost = 0;
                for(int k = 0; k < j; k++) {
                    cost += calc(a[i-k-1], b[i-perm[k]-1]);
                }
                dp[i] = min(dp[i], dp[i-j] + cost);
            } while(next_permutation(perm, perm + j));
        }
    }
    cout << dp[N];
}

 

 

 

이제 dp, 그래프 편식 그만하고 다른 것들도 좀 풀자;;