[APIO] 백준 1150 - 백업

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

전개

언뜻 보면 가장 짧은 거리만 취하면 되는 그리디로 보인다. 하지만 문제의 예제에서는 가장 짧은 경우인 회사 2 - 회사 3을 선택하고 있지 않다.

 

만약 {2, 3}를 택하게 되면 {1, 2}와 {3, 4}를 쓰지 못하게 되고 여기서 괜찮은 경우가 있을 수 있으므로 완벽한 최적해를 찾을 수 없다.

 

이를 거꾸로 보면 {2, 3}을 포기하면 {1, 2}와 {3, 4}를 챙길 수 있다는 말이 된다.

 

우리는 여기서 다음과 같은 전략을 생각해볼 수 있다.

 

일단 값이 작은 쌍을 가져가되, 상황에 따라 해당 쌍을 버리고 옆의 두 쌍을 취하기

 

그러면 예제를 완벽히 설명할 수 있다.

 

1. 일단 {2, 3}을 가져간다. 그러면 한 쌍이 연결된다.

 

2. {2, 3}을 버리고 {1, 2}, {3, 4}를 가져가는 경우와 나머지 연결되지 않은 쌍을 살펴본다. 이때 {1, 2}, {3, 4}를 취하는 쪽이 제일 작다.

 

3. {2, 3}을 버리고 {1, 2}, {3, 4}를 가져간다. 이러면 두 쌍이 연결되고 최적해 4가 된다.

 

이런 과정을 통해 k 쌍을 가져가도록 하면 된다.

유효성

만약 원래 있던 쌍을 버리는 행동을 계속할 경우 중간의 쌍들이 계속 버려지고 옆으로만 가는 일이 생기지 않냐는 의문이 생길 수 있지만 문제 조건에서 k는 n / 2 이하라는 조건이 있다. 이는 원래 쌍을 버리는 행위는 계속 반복될 수 없음을 의미한다.(해당 쌍을 버리는 것보다 다른 쌍을 가져가는 게 나은 경우를 고려하면 이해할 수 있다.)

구현

i와 i - 1 사이의 거리를 저장하도록 한다. 추가로 out of bound를 방지하기 위해 {0, 1}과 {n, n + 1}의 거리를 inf값으로 둔다.

 

그리고 우리는 이를 min heap으로 관리하면서 k 쌍을 확보할 것이다.

 

그리고 옆의 쌍을 가져가는 행동을 구현하기 위해 현재 회사 i에 대해 점거되지 않고 제일 가까운 왼쪽 회사의 위치와 점거되지 않고 제일 가까운 오른쪽 회사의 위치를 배열 $L$과 $R$로 관리할 것이다.

 

위들을 통해 min heap에는 다음과 같은 정보가 담긴다.

 

연결된 회사 덩어리들의 중심 회사 위치와 그들을 연결하는 값

 

min heap으로 값을 꺼내면서 해당 회사가 점거된 경우 건너뛰고 점거되지 않았으면 해당 가중치를 더한다.

 

그리고 해당 쌍보다 양 옆 쌍을 먹는 경우가 최적인 경우를 고려하여 양 옆 쌍을 먹는 가중치를 다시 계산하여 가중치 배열에 반영하도록 한 뒤 해상 회사가 점거되었음을(힙에 들어갈 것이므로) 표시한다.

 

그러면 $L$과 $R$을 갱신해야 한다. i 기준으로는 옆으로 한칸씩 더 밀어야 하고 이때 밀린 인덱스에 대해 $L[R[i]] = i, R[L[i]] = i$처럼 다시 다른 쪽에 가까운 회사를 i로 지정하도록 한다.

 

왜냐하면 이때 한 번 더 갱신하면 다시 i를 점거하는 것이기 때문이다. 이 이유로 인해 i는 지금 당장 표시하지 않는 것이다.

 

이는 포함 배제 원리로 설명할 수도 있는데 조악한 그림으로는 다음과 같이 표현할 수 있다.

그림에 따라 포함 배제 연산은 최대 2번 시행될 수 있다. 물론 앞서 언급한 유효성 문단에서 여기서 더 확장하는 일은 일어나지 않는다. 그럴 바에야 이미 새로운 쌍을 가져가게 되기 때문

 

아무튼 이렇게 최적의 k 쌍을 선택하면 구현이 끝나게 된다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int n, k;
bitset<100002> dominated;
int ar[100001];
int l[100001];
int r[100001];
int dl[100002];
priority_queue<pii, vector<pii>, greater<>> pq;
 
void solve()
{
  cin >> n >> k;
 
  for (int i = 1; i <= n; i++)
  {
    cin >> ar[i];
    l[i] = i - 1;
    r[i] = i + 1;
 
    if (i > 1)
    {
      dl[i] = ar[i] - ar[i - 1];
      pq.push({dl[i], i});
    }
  }
 
  l[n + 1] = n;
  dl[1] = dl[n + 1] = 1e9;
  pq.push({dl[1], 1});
  pq.push({dl[n + 1], n + 1});
 
  int ans = 0;
  int cnt = 0;
  while (cnt < k)
  {
    auto [fee, i] = pq.top();
    pq.pop();
 
    if (dominated[i]) continue;
 
    ++cnt;
    ans += fee;
 
    dl[i] = dl[r[i]] + dl[l[i]] - dl[i];
    pq.push({dl[i], i});
 
    dominated.set(l[i]);
    dominated.set(r[i]);
    r[i] = r[r[i]];
    l[i] = l[l[i]];
    r[l[i]] = l[r[i]] = i;
  }
 
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록

라면 사기보다 어려운 것 같다.

여담

탐욕적 방법의 정당성 증명은 MCMF로 한다고 한다.