BJ2565 전깃줄

풀이

input의 최대는 100개의 숫자이고 숫자의 범위는 500이하였다.

처음에 생각했던 풀이는 백트래킹에서 DP를 사용하려고 했었다.

n번째부터 마지막까지 전깃줄이 꼬이지 않도록 제거해야 하는 전깃줄의 최솟값을 메모하려했다.

하지만 이를 활용해서 다음 정답을 만드는 점화식이 성립하지 않는다는 생각이 들었다.

A를 기준으로 정렬했을 때 B에서 LIS를 구하면 전깃줄이 꼬이지 않게 된다.

그래서 LIS를 구하고 이 길이를 전체 길이에서 뺀 값이 정답이 된다.

LIS를 구하는 DP 알고리즘은 다음과 같이 구현하였다.

1. 1번째 숫자부터 N번째 숫자까지 돌면서 LIS를 구한다.

2. K번째 숫자를 맨 오른쪽 끝으로 하는 LIS를 DP배열에 메모한다.

   1. K번째 숫자보다 작은 숫자들의 DP를 모두 탐색한다.

   2. 그 중 가장 긴 값을 찾는다.

      가장 긴 값은 K번째 숫자보다 작은 숫자들로 이루어진 부분 LIS이며 여기에 1을 더한 것이 K번째 숫자를 맨 오른쪽으로 하는 LIS가 된다.

3. 1번째 숫자부터 N번째 숫자를 맨 끝으로 하는 LIS 중 가장 긴 값을 찾고 전체길이(N)에서 뺀 값을 리턴하여 출력한다.

코드

//! 2020.03.16
// TODO BJ2565_전깃줄
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int MAX = 505;
const int INF = 987654321;
int N;
vector <pair<int,int>> inData;
int DP[MAX];

int getMax(int number){
    int ret = 0;
    for(int i=1;i<number;i++){
        if(ret<DP[i]) ret = DP[i];
    }
    return ret;
}

int getResult(){
    int maxLen = -1;
    for(int i=0;i<N;i++) DP[inData[i].second] = getMax(inData[i].second)+1;
    for(int i=0;i<N;i++){
        if(maxLen<DP[inData[i].second]) maxLen = DP[inData[i].second];
        // printf("number : %d, DP : %d\n",inData[i].second,DP[inData[i].second]);
    }
    return N-maxLen;   
}

int main(){
    // freopen("input.txt","r",stdin);
    scanf("%d",&N);
    for(int n=0;n<N;n++){
        int A,B;
        scanf("%d %d",&A,&B);
        inData.push_back(make_pair(A,B));
    }
    sort(inData.begin(),inData.end());
    for(int i=0;i<=N;i++) DP[i] = -1;
    printf("%d\n",getResult());
    return 0;
}