[C++] 백준 2565. 전깃줄

🌽 문제

🥕 입출력

🥔 풀이

증가하는 수열 문제의 응용 버전이다.
입력을 vector<pair<int, int>>로 받은 뒤 오름차순 정렬한다.
그러면 vector의 second값이 증가하는 수열이어야
전깃줄이 겹치지 않는다는 걸 알 수 있다.

정렬된 vector의 second값 기준으로 가장 긴 증가하는 수열의 길이를 구한 뒤,
전체 연결된 전기줄 수에서 빼면 답을 구할 수 있다.

🥬 코드

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

int dp[101]; // dp[i]: v[i].second로 끝나는 증가하는 수열의 길이

int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> v(n);
	vector<int> dp(n, 1);

	for (int i = 0; i < n; i++)
		cin >> v[i].first >> v[i].second;

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

	for (int i = 1; i < v.size(); i++) {
		for (int j = 0; j < i; j++) {
			if (v[i].second > v[j].second) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}

	int maxi = 0;
	for (int i = 0; i < dp.size(); i++) {
		maxi = max(maxi, dp[i]);
	}
	
	int ans = n - maxi;
	cout << ans;

	return 0;
}

🥜 채점

모든 전깃줄이 연결됐다고 한 적은 없다.
for문이 n까지가 아니라 vector의 size()까지 돌도록 만들자.