[백준 2565] 전깃줄

문제 링크 => 2565번: 전깃줄 (acmicpc.net)

2565번: 전깃줄

 

다이나믹 프로그래밍 문제이다.

 

최대 전깃줄이 되도록 하려면 B전봇대로 연결된 전깃줄 중에 오름차순으로 연결될 수 있는 경우 중에 

최댓값을 구해줘야 한다.

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int dp[501];

bool compare(pair<int, int> x, pair<int, int> y) {
	return x.first < y.first;
}

int max(int x, int y) {
	return x > y ? x : y;
}

int solution(vector<pair<int,int>> v, int n) 
{
	int i, j, ret;

	sort(v.begin(), v.end(), compare);
	ret = dp[1] = 1;
	for (i = 2; i <= n; i++) {
		for (j = 1; j <= i - 1; j++) {
			dp[i] = max(dp[i], v[i - 1].second > v[j - 1].second ? dp[j] + 1 : 1);
		}
		ret = max(ret, dp[i]);
	}

	return n - ret;
}

int main(int argc, char* argv[]) 
{
	int i, n, x;
	vector<pair<int, int>> v;
	int A[501];

	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d %d", &x, &A[i]);
		v.push_back({ x,A[i] });
	}

	printf("%d", solution(v, n));

	return 0;
}