BOJ 1150 백업

사용한 알고리즘

그리디 알고리즘

알고리즘 설명

최소한의 전선길이를 이용하여 모든 짝을 지어주어야 한다.
각 빌딩 좌우 간에 길이를 계산한다.
하나의 빌딩 짝을 연결하면 그 빌딩짝 좌우에 있던 빌딩과는 짝을 이룰 수 없다.

cost: c

좌우의 빌딩과 짝을 이루기 위해서는 현재 빌딩짝 거리를 잘라낸 뒤에 좌우의 연결을 해주면 된다.

cost: b + d - c

다음에 a,e를 선택하기 위해서 들어가는 비용은 a + e - b - d + c임을 알 수 있다.
위를 이용하여 하나의 페어를 추가하기 위해서 드는 비용은 좌측 길이 + 우측 길이 - 현재 길이임을 알 수 있다.
위 공식을 이용하여 가장 작은 비용을 가지는 길이를 힙에서 찾아가는 알고리즘 형태이다.
합쳐진 부분을 접근하지 않기 위해서, visited 배열을 이용하여 이미 합쳐진 장소는 접근하지 않도록 한다.
합쳐진 뒤에 이를 확인할 수 있도록 좌우에 어느 인덱스가 위치하는지를 배열을 이용하여 표현한다.
합치는 경우 현재의 좌우는 그 좌우에 있던 좌우 값으로 변해야 하고, 바꿘 좌우값들은 현재 장소를 우측 좌측으로 업데이트 해주어야 한다.
K개의 페어를 만든 뒤 결과를 출력한다.

풀이

// baekjoon 1150 yechan
#include <cstdio>
#include <algorithm>
#include <queue>
#include <functional>
#include <utility>
#include <vector>
using namespace std;
const int MAX_N=100002;
const int MAX_INF=1e9;
typedef pair<int, int> Pii; // <dist, <start, end>>
int N, K, S1, S2;
int dist[MAX_N];
int left[MAX_N], right[MAX_N];
bool visited[MAX_N];
priority_queue<Pii, vector<Pii>, greater<Pii> > PQ;

int main() {
	scanf("%d%d", &N, &K);

	dist[1]=dist[N+1]=MAX_INF;
	right[1]=2;
	left[N+1]=N;
	PQ.push({MAX_INF, 1});
	PQ.push({MAX_INF, N+1});

	scanf("%d", &S1);
	for (int i=2; i<=N; i++) {
		scanf("%d", &S2);
		dist[i]=S2-S1;
		PQ.push({dist[i], i});
		left[i]=i-1;
		right[i]=i+1;
		S1=S2;
	}
	int ret=0;

	while (K--) {
		while (visited[PQ.top().second]) PQ.pop();
		int d = PQ.top().first;
		int idx = PQ.top().second;
		PQ.pop();
		ret += d;
		dist[idx] = dist[left[idx]] + dist[right[idx]] - dist[idx];
		PQ.push({dist[idx], idx});
		visited[left[idx]] = visited[right[idx]] = true;
		left[idx] = left[left[idx]];
		right[idx] = right[right[idx]];
		right[left[idx]] = idx;
		left[right[idx]] = idx;
	}
	printf("%d\n", ret);
	return 0;
}