[BAEKJOON] 2565 전깃줄 (C++)

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

2565번: 전깃줄

문제

그림과 같이 전깃줄이 연결돼있을 때 겹치는 부분을 최소화 할 수 있도록 일부 전깃줄을 제거할 때, 최소한으로 제거하는 경우를 생각하는 문제이다.

각각이 몇개가 겹치는지를 파악해서 해결하려하면 막막하다.(두 자신이 겹치는 전깃줄이 무엇인지 모두 생각해야한다.)

따라서 이 문제는 최대로 설치할 수 있는 개수를 구한 후 전체 개수에서 빼주는 것이 현명한 접근 방법인 것 같다.

 

풀이

먼저 그리디하게 풀 수 없는 이유는 전깃줄을 시작점 기준 순서대로 확인한다고 했을 때, 자기 이후의 전깃줄들을 확인하지 않고는 해당 전깃줄을 설치하는 것이 최선인지 판단할 수 없다.

따라서 DP문제이다. (사실 DP문제인 걸 알고 접근하긴 했다.)

DP문제인 걸 알고 접근했기 때문에 어떻게 dp배열을 구성할 것인지에 대해서 고민했다.

 

처음 생각은 DP[N][2]형태로 배열을 선언하고, i번째 전깃줄을 설치하는 경우와 설치하지 않는 경우로 나누어서 값을 업데이트하고 이용하려고 했다.

하지만 이 경우에는 i번째 전깃줄을 설치하려고 할 때, 이전의 전깃줄들이 도착하는 지점들을 모두 확인하면서 최댓값을 찾아야한다. 좀 복잡해지고 풀 수 있을 거란 확신이 안 들었다. (이렇게 해도 되긴 됐을 것 같다.)

 

두번째로는 생각을 조금 바꿔서 도착하는 지점들을 기준으로 생각하는 것이다.

DP[N]배열에서 i번째 값이 의미하는 바는, 해당 도착지점에서 전깃줄이 설치될 수 있는 최대값이다.

시작지점을 먼저 정렬한 후 처음부터 도착지점을 확인한다. (정렬을 하지 않는 경우는 특정 전깃줄을 설치할 때 최댓값이라는 것을 보장할 수 없다 -> 이전의 전깃줄을 모두 확인한 것이 아니므로)

도착지점 이전 값들, 예를 들어 도착지점이 5 라면 1, 2, 3, 4 번째 기록된 값을 확인하고 그 중 최댓값에 +1한 값을 DP[5]에 있는 값과 비교해서 더 큰 값을 기록한다.

-> 이렇게 했을 때 해당 전깃줄을 설치하는 경우 가질 수 있는 최댓값을 얻는다.

 

 

 

다른 블로그 풀이를 봤더니 사실상 LIS 문제와 동일하다는 것을 알았다. 듣고 보니 명확한데, 떠올리기가 참 힘든 것 같다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

#define endl "\n"

using namespace std;

int N, ans;
int dp[501];
vector<pair<int, int>> V;
void Solve() {
	cin >> N;
	int a, b, maxN;
	for (int i = 1; i <= N; i++) {
		cin >> a >> b;
		V.push_back({ a,b });
	}

	sort(V.begin(), V.end());

	for (int i = 0; i < V.size(); i++) {
		maxN = 0;
		for (int j = V[i].second-1; j >= 0; j--) {
			maxN = max(maxN, dp[j]);
		}
		dp[V[i].second] = max(dp[V[i].second], maxN + 1);
		ans = max(ans, dp[V[i].second]);
	}

	cout << N-ans;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "r", stdin);
	Solve();


	return 0;
}