백준 2565번: 전깃줄 (C++)

Melonpanna·2022년 12월 1일

1. 문제 링크

2. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int longest[505];
	vector<pair<int, int>> v;
	int n,a,b;
	cin >> n;
	for (int i = 0;i < n;i++) {
		cin >> a >> b;
		v.push_back(make_pair(a, b));
	}
	sort(v.begin(), v.end());
	for (int i = 0;i < n;i++) {
		longest[i] = 1;
		for (int j = 0;j < i;j++) {
			if (v[j].first < v[i].first && v[j].second < v[i].second) {
				longest[i] = max(longest[i], longest[j] + 1);
			}
		}
	}
	int ans = longest[0];
	for (int i = 1;i < n;i++)if (longest[i] > ans)ans = longest[i];
	cout << n-ans;
	return 0;
}

3. 노트

3-1.첫 번째 시도 (실패)

처음에 문제를 봤을 때는 이게 다이나믹이라고? 탐욕법이 아니고? 라고 생각했다. 알고리즘 분류 말고 문제만 봤을 때는 다른 선과의 교점의 개수가 많은 선부터 제거하거나, 아니면 기울기가 커서 다른 선들과 교차할 확률이 많은 선부터 제거하려고 생각했었다. 하지만 교점의 개수가 많은 선부터 제거하자니 남은 교점의 수를 업데이트하는 과정에서 시간 낭비가 컸고, 기울기가 큰 선부터 제거하자니 반례부터 생각났다.

3-2.Dynamic programming

Dynamic programming은 왜 dynamic programming이냐!
그냥 이 알고리즘 만든 사람이 dynamic이라는 단어를 좋아해서라고 한다. 나는 Dynamic programming을 간단하게 이전 단계의 연산 결과를 현 단계의 연산에 이용하여, 같은 연산을 되풀이하지 않아 시간 효율성을 추구하는 방식이라고 이해했다.

3-3.DP-LIS(최장 증가 부분 수열, Longest Increasing Sequence) 알고리즘

위키백과에 따르면 LIS는 주어진 수열 속에서, 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제로 DP를 사용하여 풀 수 있다.
글로 설명해 보자면 주어진 수열에서 인덱스를 한 칸씩 증가시키며 그 인덱스까지의 가장 긴 부분수열의 길이를 저장하는데, 이전 단계들의 가장 긴 부분수열의 길이를 이용하여, 현 인덱스까지의 가장 긴 부분수열의 길이를 업데이트한다. 코드를 보면 이 알고리즘의 시간복잡도는 O(n^2)인데 이 문제에서의 n의 최댓값이 (일반적인 문제들에 비해) 상대적으로 작아 이 알고리즘으로 해결할 수 있다.