[BOJ 2984] 고속도로

문제

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

2984번: 고속도로

 

---

알고리즘

• DP

---

풀이

입력에서 맨 처음에 \(N\)을 입력받은 후, \(N\)개의 쌍이 주어지는데, 각 \(i\)번째 쌍에서 첫 번째 수를 \(a_i\), 두 번째 수를 \(b_i\)라고 하겠습니다.

 

이번 문제는 간단하게 말하자면 입력받은 배열 \(a\)와 \(b\)를 적절히 재배치해서 새로운 쌍들을 만들었을 때 각 쌍의 두 수의 차의 합이 최소가 되게끔 만드는 문제입니다.

그냥 두 배열을 정렬하면 될 듯 싶지만 쌍의 두 수가 같으면 안 됩니다. 그러므로, 먼저 두 배열을 정렬한 다음 한쪽 배열의 수들을 적절히 바꿔 조건을 만족하면서 구한 값이 최소가 되게 해야 합니다.

 

처음 봤을땐 머리가 하얘질 수 있지만, 조금만 생각해보면 간단한 풀이를 찾을 수 있습니다.

먼저, \(a_i\)와 \(b_i\)가 같지 않다면 바꾸지 않고 그냥 놔두는 경우를 생각할 수 있습니다.

바꾸는 경우를 생각하면, 멀리 있는 수와 바꾸면 오히려 손해이므로, 인접해 있는 수들과 바꾸는 경우를 생각해 총 3가지를 생각할 수 있습니다:

 

1. 바로 앞의 수와 바꾸는 경우.
2. 자신과 바로 앞의 수를 한 칸씩 앞으로 옮기고 두 칸 앞에 있었던 수를 자신의 위치로 옮기는 경우.
3. 자신 바로 앞의 수와 두 칸 앞의 수를 한 칸씩 뒤로 옮기고 자신을 두 칸 앞의 위치로 옮기는 경우.

첫 번째 경우만 생각해도 된다고 생각할 수 있지만, 2번 예제에서 그렇게 해 버리면 한 쌍의 두 수가 같아지게 되므로 3개의 수를 바꾸는 방법 중 효율적인 두 방법을 선택해 추가했습니다.

 

이것까지 생각했다면 이제 구현만 하면 됩니다.

\(dp\)배열은 당연히 다음과 같이 정의할 수 있습니다:

 

• \(dp[i]:\) \(i\)번째 쌍까지 고려했고 조건을 만족하면서 구한 값이 최솟값이 되도록 수들을 재배치했을 때 그 구한 값.

점화식은 다음과 같이 세울 수 있습니다:

$$dp[i] = \min\begin{cases}
dp[i - 1] + |a_i - b_i|, & \text{ where } a_i \neq b_i\\ 
dp[i - 2] + |a_i - b_{i - 1}| + |a_{i - 1} - b_i|\\ 
dp[i - 3] + |a_{i - 1} - b_{i - 2}| + |a_i - b_{i - 1}| + |a_{i - 2} - b_i|\\ 
dp[i - 3] + |a_{i - 1} - b_i| + |a_{i - 2} - b_{i - 1}| + |a_i - b_{i - 2}|
\end{cases}$$

답은 끝까지 고려했을 때이므로, \(dp[N]\)이 그 값이 됩니다.

 

시간복잡도: \(O(N \log N)\)

 

---

전체 코드

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    vector<ll> a(N + 1), b(N + 1), dp(N + 1, 1e18);
    for (int i = 1; i <= N; ++i) cin >> a[i] >> b[i];
    sort(all(a)), sort(all(b));

    dp[0] = 0;
    for (int i = 1; i <= N; ++i) {
        if (a[i] != b[i]) dp[i] = dp[i - 1] + abs(a[i] - b[i]);
        if (i >= 2) dp[i] = min(dp[i], dp[i - 2] + abs(a[i] - b[i - 1]) + abs(a[i - 1] - b[i]));
        if (i >= 3) {
            dp[i] = min({
                dp[i],
                dp[i - 3] + abs(a[i - 1] - b[i - 2]) + abs(a[i] - b[i - 1]) + abs(a[i - 2] - b[i]),
                dp[i - 3] + abs(a[i - 1] - b[i]) + abs(a[i - 2] - b[i - 1]) + abs(a[i] - b[i - 2])
            });
        }
    }

    cout << dp[N] << '\n';

    return 0;
}