728x90
반응형
목차
https://www.acmicpc.net/problem/2565
문제
문제 구현 방향
생각보다 아이디어가 잘 떠오르지 않는다. 나도 처음에는 막혀서 답을 보아버렸다..
아이디어는 총 세개이다.
1. 오른쪽 기준으로 정렬하기 -> 경우를 더 줄어야 한다.
2. 전깃줄을 교차하지 않기 위한 전깃줄의 최대 개수 구하기로 바꾸어 생각하기
-> 이렇게 생각하면 아래와 같은 문제로 변한다.
3. 증가하는 가장 긴 부분수열 구하기
참고
https://be-senior-developer.tistory.com/23
위에 문제를 풀어보았음에도 오래되어 생각이 잘 나지 않았다. 위의 문제를 풀어보면 더 쉽게 접근 할 수 있다.
코드 구현
#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>
using namespace std;
int N, a, b;
vector<pair<int, int>>v;
int arr[502] = { 0 };
int dp[502] = { 0 };
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> a >> b;
v.push_back({ b, a });
}
sort(v.begin(), v.end());
dp[0] = 1;
for (int i = 0; i < v.size(); i++) {
int prev = 0;
for (int j = 0; j <i; j++) {
if (i == 0)continue;
if(v[i].second >= v[j].second){
prev = max(dp[j], prev);
}
}
dp[i] = prev + 1;
}
cout << N - *max_element(dp, dp+502);
return 0;
}
반응형
'백준 문제풀이' 카테고리의 다른 글
[백준][백트래킹][브루트포스] 15683 감시 c++구현 (0) | 2024.09.19 |
---|---|
[백준][누적합][구현] 27942 danceplant c++ 구현 (1) | 2024.09.19 |
[백준][스위핑] 1931 회의실 배정 c++구현 (0) | 2024.09.15 |
[백준][스위핑] 2170 선 긋기 c++구현 (0) | 2024.08.24 |
[백준][이분탐색] 2632 피자판매 c++구현 (0) | 2024.08.19 |