백준 2565 전깃줄 쉬운 풀이(C++/CPP)

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

문제 추상화

• DP로 LCS를 구하는 문제
  • LCS : 붙어있지 않고도 점점 증가하는 수열의 최대 개수
  • 참조 : https://www.acmicpc.net/problem/9251
• LCS인 이유
  • 전깃줄이 교차하지 않아야함
  • A이나 B중 하나를 정렬하면
  • 전깃줄이 교차하지 않으면 나머지 것이 순차적으로 증가와 같음

아이디어

• DP로 LCS 풀기
  • DP[i] = i번째 위치에서 LCS 개수
  • 처음에 DP[i]를 1로 초기화
  • DP[i] = for(j=0~i-1) if(num[i] > num[j]) DP[i] = max(Dp[i], DP[j]+1)

시간복잡도 계산

• O(N^2) : 1e4
• 만약 숫자 클경우 이진탐색을 통해서 풀경우 O(NlgN)으로 가능

인트 계산

• 전깃출 최대 100
• 위치 최대 500
• 모두 INT 사용 가능

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
pair<int, int> nums[110];
int dp[110];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(dp, dp+110, 1);
    int N; cin >> N;
    for(int i=0; i<N; i++) {
        int a,b; cin >> a >> b;
        nums[i] = make_pair(a,b);
    }
    
    sort(nums, nums+N);
    int maxv= 1;
    for(int i=1; i<N; i++) {
        for(int j=0; j<i; j++) {
            if(nums[i].second > nums[j].second) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        maxv = max(maxv, dp[i]);
    }
    
    cout << N-maxv << '\n';
    
    return 0;
}
 

문제유형

• 끝에서부터 시작하는 DP
  • DP에서 순차적으로 오는것이 아닌, 여러 경로가 있을떄 사용
  • 특히 2차원에서 상하좌우를 모두 고려해줘야할 때

비슷한 문제

• DP - LCS