백준 2565번 : 전깃줄

문제 링크 : www.acmicpc.net/problem/2565

풀이에 참고한 링크 : www.acmicpc.net/board/view/8218

내 풀이(2021.2.3.) : DP

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<pair<int, int>> p;
vector<int> v;
vector<int> dp(500, 1);

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

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int a, b; cin >> a >> b;
		p.push_back(make_pair(a, b));
	}

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

	for (int i = 0; i < N; i++) {
		v.push_back(p[i].second);
	}

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

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

	return 0;
}

- '가장 긴 증가하는 부분 수열'을 이용한다는 아이디어가 필요했다.

- DP들의 초기값을 1로 초기화해야 했다.

- 정답은 마지막 번째 DP 값이 아닌, 모든 DP 값들 중 최댓값이었다.

- 벡터의 초기화시, 인자의 순서 주의 : 1번째 인자는 벡터의 크기, 2번째 인자는 초기화할 값