백준 #2565. 전깃줄

백준 #2565. 전깃줄

정리

• 처음에는 각 전깃줄 당 교차하는 전깃줄의 개수를 구해 두고, 이를 이용하려 했으나, 고민 끝에 옳게 된 풀이 방향이 아니라는 것을 깨달았다.

• 실마리를 못 잡고 있다가, 질문 검색에서 “LIS 알고리즘을 이용하면 간단하게 풀리네요”라는 말을 봐 버렸다 ...;;;

• 전깃줄이 교차하지 않는 것들만 냅두고 없애려면, A전봇대의 위치에 따른 전깃줄의 순서와 B전봇대의 위치에 따른 전깃줄의 순서가 똑같아야 한다.

• 정렬을 해 두면 문제를 쉽게 해결할 수 있다. 전깃줄을 A전봇대의 위치를 기준으로 정렬해 두고, 루프를 돌며 교차하지 않는 전깃줄의 개수의 최댓값을 dp배열에 저장해 두는 방식으로 문제를 해결했다.

• ‘LIS 알고리즘'이라는 알고리즘의 존재를 이번 문제를 풀면서 처음 알게 되었다. 관련해서 내용 정리해 둬야겠다.
  
  

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void) {
    int n;
    int curA;
    vector<int> posA;           // A전봇대의 위치를 받기 위한 vector
    int posB[501] = {0, };      // A전봇대의 위치에 따른 B전봇대의 위치를 저장해 두기 위한 array
    int dp[101];
    int res = 0;
    
    posA.push_back(0);
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>curA;
        cin>>posB[curA];
        posA.push_back(curA);
        dp[i] = 1;
    }
    sort(posA.begin(), posA.end());
    
    dp[1] = 1;
    res = 1;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<i; j++) {
            if (posA[i] > posA[j] && posB[posA[i]] > posB[posA[j]]) {
                dp[i] = max(dp[j] + 1, dp[i]);
            }
        }
        res = max(res, dp[i]);
    }
    
    cout<<n-res<<endl;
    return 0;
}