[백준] 1150 백업

문제 주소 : www.acmicpc.net/problem/1150

1150번: 백업

문제 확인

 

그리디 알고리즘 문제입니다. 선택할 간선들을 우선순위 큐를 활용하여 짧은 순서대로 뽑고, 뽑은 위치에 왼쪽, 오른쪽 간선을 하나로 합쳐 큐에 삽입하는 형식을 통해 인접 케이스를 해결합니다.

 

풀이

 

우선순위 큐를 사용하면 간단하게 연결된 회사끼리 묶으며 짧은 쌍을 쉽게 뽑아낼 수 있습니다.

주의해야 할 점은 조건 상 한 쌍을 뽑게 되면 양 옆의 쌍을 뽑을 수 없으며, 묶은 쌍 양 옆을 잘 처리해주어야 합니다.

백준에 나와있는 예시를 통해 풀어보겠습니다.

 

예시 :

5 2

1 3 4 6 12

예시 그림

초기 우선순위 큐 상태를 그려보면 4개의 간선이 있으며 이 중 최솟값을 선택하면 B,C 쌍을 선택하게 됩니다.

B,C 쌍을 선택하면 (A,B), (C,D)을 선택하면 안 되며 큐에 존재하는 2쌍을 선택하면 안 됩니다. 하지만 실제 답은 AB, CD 쌍을 선택하는 것이 답이며 이를 해결하기 위하여 큐에 새로운 값인 AD 3을 추가합니다. 값이 3인 이유는 이미 BC 1을 선택하였기 때문에 AB, CD 값을 선택하는 것처럼 만들어 주기 위하여 AD의 값을 AD-BC로 두어야 합니다.

이러한 과정을 K개 선택할 때 까지 반복해 줍니다.

 

코드

#include <cstdio>
#include <vector>
#include <queue>
typedef struct data {
    int val, left, right;
    bool operator <(data &b)const {
        return val < b.val;
    }
}data;
struct comp {
    bool operator()(data a, data b) {
        return a.val > b.val;
    }
};
 
int main() {
    std::priority_queue<data, std::vector<data>, comp> pty_queue;
    int n, k, res = 0, p;
    data point[100001];
    scanf("%d%d%d", &n, &k, &p);
    for (int i = 1, tmp; i < n; i++) {
        scanf("%d", &tmp);
        point[i].val = tmp - p;
        point[i].left = i - 1;
        point[i].right = i + 1;
 
        pty_queue.push(data{ point[i].val , i, i + 1 });
        p = tmp;
    }
    point[n] = { 0, n - 1, n + 1 };
 
    for (int i = 0; i < k;) {
        data t = pty_queue.top();
        pty_queue.pop();
        int cl = t.left, cr = t.right;
        if (cl >= 1 && cr <= n && cr == point[cl].right && cl == point[cr].left) {
            res += t.val;
            if (++i >= k) break;
            int nl = point[cl].left, nr = point[cr].right;
            t.left = nl; t.right = nr;
            point[nl].val = point[nl].val + point[cr].val - t.val;
            t.val = point[nl].val;
            pty_queue.push(t);
            point[nl].right = nr;
            point[nr].left = nl;
 
        }
    }
    printf("%d", res);
    return 0;
}