전깃줄 (feat. 백준, 2565번)

전깃줄
https://www.acmicpc.net/problem/2565

2565번: 전깃줄

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/2565
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N, arr[500] = { 0 }, dp[501], ans = 0;
	for (register int i = 1; i <= 500; ++i)
		dp[i] = 1;
	cin >> N;
	for (register int i = 1, x, y; i <= N; ++i)
		cin >> x >> y, arr[x] = y;
	for (register int i = 1, j, tmp; i <= 500; ++i) {
		tmp = 1;
		if (arr[i] != 0)
			for (j = 1; j <= i; ++j)
				if (arr[j] != 0 && arr[i] > arr[j])
					tmp = max(tmp, dp[j] + 1);
		dp[i] = tmp;
		ans = max(ans, dp[i]);
	}
	cout << N - ans << endl;

	return 0;
}
// *&)*@*

체크하는 값이 현재 나의 값보다 작다면 삭제해야 하는 선입니다. (체크하는 값은 커지는데 검사하는 값이 더 작다면 무조건 겹치기 때문입니다.)