[백준/BOJ] 2565번 전깃줄 (C/C++)

백준 온라인 저지(BOJ) 2565번 전깃줄

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

2565번: 전깃줄

* 사용언어 : C언어, C++

 

1. 문제

2개의 전봇대에 연결되는 전깃줄의 위치 번호가 주어질 때

남아있는 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력

 

2. 풀이

LIS(Longest Increasing Subsequence)로 풀 수 있는 문제입니다.

백준 LIS 문제 설명 및 풀이는 아래 링크 참고하시면 됩니다.

https://rightbellboy.tistory.com/329

[백준/BOJ] 11053번 가장 긴 증가하는 부분 수열 (C/C++)

 

문제에서 주어진 <그림 1>을 보면서 고민을 해보니

A에 연결된 순서대로 정렬된 상태라고 생각해보니 B의 LIS를 구하면 되는 문제라는 것을 알 수 있었습니다.

 

그래서 주어진 입력에서 A를 오름차순으로 정렬하고

동일한 순서로 정렬된 B에서 LIS를 찾은 후 N에서 빼서 답을 출력했습니다.

 

저는 정렬 시 O(NlogN)의 시간 복잡도를 갖는 heap 정렬을 활용해봤습니다.

heap 정렬 사용 시 구조체 없이 int로 처리하기 위해서 a[i]를 왼쪽 shift한 후 b[i]와 합쳐서 하나의 int로 처리했습니다.

 

위치 번호는 500이하로 2^9(512)보다 작으므로 a[i]를 9만큼 shift하면 되고,

정렬이 끝난 후에는 a[i]가 필요 없으므로 heap에 저장된 값에 0x1ff(0001 1111 1111)과 & 연산을 해주면 b[i]만 남습니다.

 

나머지 설명은 아래 코드로 대체하겠습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
2565_전깃줄
KB	ms
*/
#include <cstdio>

constexpr int LM = 101;
int N, a, b, dp[LM], max;
int h[LM], hn, c;

void push(int v) {
	for (c = ++hn; c > 1 && v > h[c >> 1]; c >>= 1) h[c] = h[c >> 1];
	h[c] = v;
}

int pop() {
	int v = h[hn];
	h[hn--] = h[1];

	for (c = 2; c <= hn; c <<= 1) {
		c += (c < hn && h[c + 1] > h[c]);
		if (h[c] > v) h[c >> 1] = h[c];
		else break;
	}
	h[c >> 1] = v;

	return h[hn + 1];
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d %d", &a, &b);
		push((a << 9) | b);
	}

	while (hn > 0) pop();
	for (int i = 1; i <= N; ++i) h[i] &= 0x1ff; // 0001 1111 1111

	for (int i = 1; i <= N; ++i) {
		for (int j = 0; j < i; ++j) {
			if (h[j] < h[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
		}
		if (dp[i] > max) max = dp[i];
	}

	printf("%d\n", N - max);
	return 0;
}