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

백준 2565 : 전깃줄

난이도 : 골드 5

시간 : 28분 소요

 

 

문제

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

2565번: 전깃줄

 

풀이 과정

 

LIS(Longest Increasing Subsequence)에 대한 개념과 구현 방법에 대해서 알고 있으면 이 문제는 쉽게 풀 수 있다.

 

문제를 요약하면 교차하는 것을 제거하는 데, 제거 횟수를 최소로 하는 것이다.

 

먼저 교차에 대해 고민해볼 필요가 있다.

교차하지 않기 위해서는 <전봇대1>의 n번째 위치에서 <전봇대2>로 연결할 때 1~n-1 위치가 연결할 위치보다 높은 숫자에 연결하면 된다.

다시 말해, 증가하는 수열이면 된다는 것이다.

 

입력 값은 b[MAX] 배열로 받았다.

dp[N]을 선언하였고, 의미는 b[N]항을 해당 부분수열의 원소로 선택했을 때 가장 긴 증가하는 수열을 의미한다.

 

LIS 에 대하여 잘 알고 있다는 가정하에 진행합니다. LIS에 대해 더 알고싶으시면 아래 문제를 풀어보고 오는 것을 추천합니다.

 

2023.02.24 - [study/Algorithms] - [C++] 백준 11054 - 가장 긴 바이토닉 부분 수열

[C++] 백준 11054 - 가장 긴 바이토닉 부분 수열

 

먼저 순서를 정렬하고자, 한 줄에 두 입력값을 받으면 첫번째 값인 <전봇대1> 위치 값을 b[MAX] 배열의 인덱스로 지정하였다.

이렇게 한다면, <전봇대 2> 위치값이 순서대로 정렬될 수 있기 때문이다. 

따라서 b[MAX] 수열의 가장 긴 부분수열을 구하면 문제를 해결할 수 있다.

 

 

마무리

 

가장 긴 수열의 길이를 result 로 저장하여, 출력할 때는 전체 전깃줄에서 가장 긴 수열의 길이만 빼서 출력한다.

이는 가장 긴 수열에 포함되지 않은 요소이자 없애야 하는 전깃줄을 의미한다.

 

최종 코드

#include <iostream>
#define MAX 502

int N;
int b[MAX];
int dp[MAX];

int Max(int a, int b){
    return a>b? a : b;
}

int main(){
    scanf("%d", &N);
    
    for(int i=1; i<=N; i++){
        int tmp = 0;
        int v = 0;
        scanf("%d %d", &tmp, &v);
        b[tmp] = v;
    }
    
    int result = 0;
    for(int i=1; i<MAX-1; i++){
        if(b[i] == 0)
            continue;
        dp[i] = 1;
        for(int j=i-1; j>0; j--){
            if(b[i]>b[j])
                dp[i] = Max(dp[i], dp[j]+1);
        }
        result = Max(dp[i], result);
    }
    
    printf("%d\n", N-result);
    
}

처음에 <전봇대 2>에 연결되지 않은 것도 검사하여 틀렸고, 시간을 좀 낭비했다.

if문으로 처리해주니 정답이 됐다.

 

잡담

백준 카테고리를 들어가서 풀었기 때문에 LIS 방식으로 풀어야 겠다는 생각을 하는데 어렵지 않았다.

하지만 이런 맥락 없이 같은 문제를 풀었더라면 고민을 더 했을 것이다.

 

이제 슬슬 카테고리 식으로 푸는 것을 지양해야겠다.