[백준] 2565번 전깃줄
[백준] 2565번 전깃줄
문제 링크: https://www.acmicpc.net/problem/2565
문제
입출력
문제 접근
dp문제이고, 가장 긴 증가 수열을 구하는 문제이다.
A전봇대를 오름차순으로 정렬해놓는다. 그러면 오른쪽에 있는 전깃줄이 자기마음대로 엉켜있다. 이때, 엉켜있는 것을 없애고, 최소로 전깃줄을 없애려면, b의 가장 긴 증가수열(LIS)를 구하면 된다.
코드 구현(c++)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int cache[101];
int N;
vector<pair<int, int> > v;
int dp(int n){
int& res = cache[n];
if(res != -1) return res;
res = 1;
for(int i = n+1 ; i < N ; i++){
if(v[n].second < v[i].second) res = max(res, dp(i)+1);
}
return res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin >> N;
for(int i = 0 ; i < N ; i++){
int temp1, temp2;
cin >> temp1 >> temp2;
v.push_back(make_pair(temp1,temp2));
}
memset(cache,-1,sizeof(cache));
sort(v.begin(),v.end());
int res = 0;
for(int i = 0 ; i < N ; i++){
res = max(res, dp(i));
}
cout << N-res << "\n";
}
Author And Source
이 문제에 관하여([백준] 2565번 전깃줄), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kpg0518/백준-2565번-전깃줄저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)