[C++] 백준 2565 - 전깃줄 [Gold5]

출처

https://www.acmicpc.net/problem/2565

풀이 전략

처음엔 입력 받은 a,b 쌍을 b를 기준으로 정렬해서 시작점(a)의 크기를 비교해서 DP 값을 올려주는 방식으로 구현하려고 했으나, 그렇게 해보려고 했더니 여러가지 경우의 수가 존재하게 되어 복잡해진다는 단점이 존재했다. 그래서 a를 정렬해서 b의 크기를 비교해서 그걸 기준으로 구하는 방식으로 구하였다.

풀이

처음 시도한 풀이는 파란색 줄로 b를 정렬해서 풀려는 전략이였었는데, 이렇게 하게 될 경우 1-8, 3-9는 확정적으로 제거해야 하지만, 이 둘을 제거하고 난 뒤, 4-1과 2-2가 겹치기 때문에 2가지 경우의 수가 존재하게 된다. 어차피 최솟값을 찾는 문제이기 때문에 값은 두 경우의 수 모두 똑같이 나오게 되긴 하겠지만, 번거로움을 피하기 위해 역으로 제거해야할 전깃줄의 최솟값이 아닌 안겹치기 때문에 냅둬야할 전깃줄의 최댓값을 N에서 빼주는 전략을 사용했다.

전체에서 최댓값을 빼게 되면 결국 최솟값을 구하는 것과 같다는 원리를 이용했다.
따라서 먼저 a를 기준으로 정렬해서 일반적인 배열의 형태처럼 만든 뒤, 반복문을 돌면서 a가 큰 수의 b값이 a가 작은 값의 b값보다 클 경우 겹칠 확률이 없기 때문에 DP 값을 1씩 늘려준다. 마지막 N번째까지 반복문을 다 돌고 나면 DP 값 중에서 최댓값을 찾아서 N에서 뺀 값을 출력한다.

소스 코드

/*
# Question: BJ 2565 (https://www.acmicpc.net/problem/2565)
# Rank: Gold5
# Algorithm: DP
*/

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 501
using namespace std;
typedef pair<int, int> pii;

int N;
vector<pii> v;
vector<int> DP(MAX);

void Input(){
    cin>>N;
    DP.resize(N+1);
    for(int i=0; i<N; i++){
        int a, b;
        cin>>a>>b;
        v.push_back({a, b});
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    Input();
    sort(v.begin(), v.end()); // a를 기준으로 크기 순으로 정렬
    for(int i=0; i<N; i++){
        DP[i] = 1;
        for(int j=0; j<i; j++){
            if(v[i].second > v[j].second){
                DP[i] = max(DP[i], DP[j]+1);
            }
        }
    }
    int ans = 0;
    for(int i=0; i<N; i++){
        ans = max(ans, DP[i]);
    }
    cout<<N-ans<<endl;
    return 0;
}

결과