전깃줄 (2565)

1. 문제 링크

문제 링크

2. 풀이

(a, b)를 (A전봇대 위치, B전봇대 위치)라 명칭하고, A전봇대 입장에서 생각해봅시다.
전깃줄이 꼬이지 않으려면 어떻게 연결돼야 할까요?

• 꼬이지 않는 경우 (1, 1), (2, 3)
  두 번째 B전봇대 위치가 이전인 첫 번째 전깃줄의 B전봇대 위치보다 크기 때문에
  꼬이지 않습니다.

• 꼬이는 경우 (2, 3), (5, 1)
  두 번째 B전봇대 위치가 이전인 첫 번째 전깃줄의 B전봇대 위치보다 작기 때문에
  꼬이지 않습니다.

뭔가 떠오르지 않나요?
현재 B전봇대 위치가 이전에 설치된 전깃줄의 B전봇대 위치보다 크다면
꼬이지 않고 설치할 수 있습니다.
그렇다면 A전봇대 위치 기준으로 오름차순 정렬한 다음에
B전봇대 위치 기준으로 LIS(최장 증가 수열)을 구하면 꼬이지 않는 전깃줄의 개수를 구할 수 있습니다.

문제의 예제입니다.

8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

위 예제를 A전봇대 위치 기준으로 오름차순 정렬후 LIS를 구하면 다음과 같습니다.

1. (1, 8), (2, 2), (3, 9), (4, 1), (6, 4), (7, 6), (9, 7), (10, 10)
2. (1, 8), (2, 2), (3, 9), (4, 1), (6, 4), (7, 6), (9, 7), (10, 10)

검정색으로 강조된 부분이 LIS이고, 꼬이지 않는 전깃줄 목록입니다.
고로 전체 전깃줄의 개수 - LIS가 답이 됩니다.

3. 전체 코드

#include <bits/stdc++.h>

using namespace std;

int n;
int dp[101];
pair<int, int> p[101];

int lis(int s) {
	int &ret = dp[s];

	if (ret != 0) return ret;

	ret = 1;

	for (int i = s + 1; i <= n; i++) {
		if (p[s].second < p[i].second) ret = max(ret, 1 + lis(i));
	}

	return ret;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> p[i].first >> p[i].second;
	}

	// A 기준으로 정렬
	sort(p + 1, p + 1 + n);

	// 전체 전깃줄의 개수 - LIS
	cout << (n - lis(0) + 1);

	return 0;
}