Algorithm/dp
백준 2565 전깃줄 c++ // dp, LIS(최장부분증가수열) 풀이
Mini_96
2023. 12. 1. 16:19
https://www.acmicpc.net/problem/2565
2565번: 전깃줄
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는
www.acmicpc.net
1. LIS(최장부분증가수열) 풀이
ex)
수열 / dp값 /해당경우의수
3 / 1 / 3
5 / 2 / 3 5
1 / 1 /1
6 / 3 /3 5 6
4 / 2 /3 4 또는 1 4
일반화 : 앞에서 자기보다 작은게있다 -> 그 dp값 중 최대값 +1
행동영역 : dp문제를 LIS 문제로 해결할수 있을지 시험해보자
2. 의사코드
1. first에 대해 정렬후
2. second에 대해 최장부분증가수열 중 최대값을 구하면
그 값이 설치가능한 전깃줄의 최대갯수
3. n-ret == 제거해야하는 전깃줄의 갯수
#include <bits/stdc++.h>
using namespace std;
int n, dp[504];
vector<pair<int, int>> v;
vector<int> a;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; ++i) {
int a,b;
cin >> a>>b;
v.push_back({a,b});
}
//1. 좌측기준 정렬
sort(v.begin(), v.end());
for (auto p : v) {
//cout << p.first << " " << p.second << "\n";
a.push_back(p.second);
}
//2. LIS 문제 : 최장부분증가수열 문제로 바뀜
fill(dp, dp + 504, 1); //초기값 : 1(자기자신부터 시작하면 길이 1임)
for (int i = 1; i < n; ++i) { //대상
//뒤에서 자기보다 작은것이 있다면 그중 최대값+1 이 답임.
priority_queue<int> pq;
for (int j = i-1; j >= 0; --j) {
if (a[i] > a[j]) pq.push(dp[j]);
}
if (pq.size()) dp[i] = pq.top()+1;
}
//for (int i = 0; i < n; ++i) cout << dp[i] << " ";
//답 : 전체전깃줄갯수 - 설치가능한 최대갯수 == 없애야하는 갯수
cout << n- *max_element(dp,dp+n);
return 0;
}