백준2984 고속도로

작성일 | In

문제 링크

  • http://icpc.me/2984

문제 출처

  • 2007/2008 COCI Contest #6 6번

사용 알고리즘

  • DP

시간복잡도

  • $O(N \log N)$

풀이

들어온 나들목의 번호와 나가는 나들목의 번호를 각각 정렬하고 생각해도 상관 없습니다.

티켓에 적혀있는 번호와 같은 나들목으로 나갈 수 있다면 정렬해서 하나씩 매칭해주는 쉬운 문제입니다. 하지만 이 문제에서는 티켓에 적혀있는 번호와 다른 나들목으로 나가야만 합니다.
이럴 때는 앞뒤 하나씩만 더 봐주면서 DP를 해주면 됩니다. 앞뒤 하나씩, 총 3개를 보면 그 중 하나는 같은 번호의 나들목으로 안 나가기 때문에 문제를 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int n;
ll a[101010], b[101010];
ll dp[101010], chk[3];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i] >> b[i];
    sort(a+1, a+n+1); sort(b+1, b+n+1);
    memset(dp, 0x3f, sizeof dp); dp[0] = 0;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=3; j++) if(i-j+1 >= 1){
                for(int k=0; k<j; k++) chk[k] = k;
                do{
                    ll now = 0, flag = 1;
                    for(int k=0; k<j; k++){
                        auto t = abs(a[i-k] - b[i-chk[k]]);
                        if(t) now += t;
                        else flag = 0;
                    }
                    if(flag) dp[i] = min(dp[i], dp[i-j] + now);
                }while(next_permutation(chk, chk+j));
            }
    }
    cout << dp[n];
}