(백준/C++) 2565_전깃줄

2565번: 전깃줄 문제는 동적 계획법 문제이지만, 문제 풀이를 생각해내기 어려운 문제라고 생각됩니다.

동적 계획법(Dynamic Programming, DP)이란, 큰 문제를 작은 문제들로 나누어 풀어나가고 작은 문제의 해를 저장해 다시 계산하지 않고 사용하는 방식입니다.

우선, 이 문제도 동적 계획법 문제이기 때문에 최적 부분 구조와 중복된 부분 문제의 두 가지 속성을 가집니다. 이 문제도 최적 부분 구조와 중복된 부분 문제에 대해 먼저 생각해보겠습니다.

1. 최적 부분 구조: 최적 부분 구조는 큰 문제의 최적 해가 작은 부분으로 나눈 하위 문제의 최적 해로부터 구성될 수 있는 것을 말합니다.
   전깃줄 문제에서는 서로 교차하지 않는 전깃줄 집합을 찾아야 합니다.
   이를 위해 전깃줄의 일부 집합에 대해 최적 해를 찾고, 이 해를 이용해 전체 문제의 최적 해를 찾을 수 있어야 합니다.
   예를 들면, 하나의 겹치지 않는 전깃줄에서부터 같은 집합에 속한 전깃줄들을 선택해가는 구조가 될 수 있습니다.
2. 중복된 부분 문제: 중복된 부분 문제는 큰 문제를 작은 부분으로 나눌 때 동일한 하위 문제가 여러 번 발생함을 의미합니다.
   전깃줄 문제에서는 전깃줄의 특정 부분에 대해 중복 계산을 해야 할 수 있습니다.
   예를 들면, 겹치지 않는 집합의 전깃줄을 구하는 과정에서 중복 계산이 있을 수 있습니다.

---

접근법

결과부터 말하자면, 이 문제는 다른 동적 계획법 문제인 “가장 긴 증가하는 부분 수열” (LIS, Longest Increasing Subsequence) 문제로 볼 수 있습니다.

만약 가장 긴 증가하는 부분 수열 문제를 풀지 않으셨다면 이 문제부터 푸시는 것을 추천 드립니다.

11053번: 가장 긴 증가하는 부분 수열

우선 이 문제는 겹치지 않는 선을 찾는다는 생각으로 접근하면 좋을 것 같습니다.

예를 들어, 이 문제의 이미지를 보고 설명드리자면, A 전봇대의 1번 전깃줄부터 시작해서 {A1, A3, A10}을 같은 그룹으로 볼 수도 있고, B 전봇대의 1번 전깃줄부터 시작해서 {B1, B4, B6, B7, B10} 같은 그룹으로도 볼 수도 있을 것 같습니다.

하지만, 여기에서 중요한 사실은 겹치지 않는 그룹을 만들기 위해서는 같은 방향에 있는 요소들끼리 묶여야 한다는 것입니다.

즉, A 전봇대의 전깃줄 번호가 증가하면 B 전봇대의 전깃줄 번호도 같이 증가해야 한다는 사실입니다.

만약, 같이 증가하다가 갑자기 B 전봇대의 번호가 줄어드는 상황이 생기면 그 전깃줄은 겹치는 상황으로 다른 그룹에 속해야 합니다.

사실 이것만으로 문제를 풀기는 어려울 수 있습니다. 따라서 한 가지 조건을 더 보고 가겠습니다.

우리는 전깃줄이 겹치는지 아닌지를 판단만 하는 것도 아니고 그룹을 만들어서 그룹별로 출력하는 것도 아닙니다.

전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 문제입니다.

즉, 그룹을 만들 수 있는 경우의 수 중에서 최대한의 수를 가지고 현재 전깃줄의 개수에서 최대 그룹의 수를 빼면 잘라야 하는 전깃줄의 개수를 구할 수 있습니다.

쉽게 말하자면 교차하지 않는 최대한의 전깃줄의 개수를 구해야 합니다.

---

풀이

교차하지 않는 최대한의 전깃줄의 개수를 구하는 방법은 가장 긴 증가하는 수열을 구하는 것과 같습니다.

다만, 문제에서 주어지는 A 전봇대와 B 전봇대의 전깃줄이 순서대로 들어오지 않기 때문에, 정렬해서 순서를 만들어주고, 그 순서대로 B 전봇대에 연결되는 전깃줄의 증가하는 수열을 구해주면 됩니다.

즉, A 전봇대에 연결된 전깃줄을 순차적으로 탐색하면서 B 전봇대에 연결된 숫자들을 가지고 가장 긴 증가하는 수열을 구하는 문제입니다.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;
	vector<pair<int, int>> connected(N);
	vector<int> length(N, 1);

	for(int i = 0; i < N; i++)
	{
		cin >> connected[i].first >> connected[i].second;
	}

	//전봇대 A의 연결 순서로 정렬
	sort(connected.begin(), connected.end());

	//LIS로 계산
	for (int i = 1; i < N; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (connected[i].second > connected[j].second)
				length[i] = max(length[i], length[j] + 1);
		}
	}

	cout << N - *max_element(length.begin(), length.end());
}

max_element는 <algorithm> 헤더에 있는 iterator의 최대 값을 가진 iterator를 리턴하는 함수입니다.

iterator를 리턴하기 때문에 포인터 연산자로 값을 가져옵니다.