[백준]_2565번 : 전깃줄(파이썬 and C언어)

2565번: 전깃줄

아이디어만 잘 찾으면 풀기 쉬웠던 문제였다. 다만 LIS(Longest Increasing Subsequence)와 이 문제가 무슨 연관이 있는지 떠올리는 데에 시간의 대부분을 할애했다.

 

접근

전깃줄이 꼬이지 않게 하기 위해서는 어떤 특징이 있을까? 먼저 예제에서 언급한 대로 전깃줄 3개를 한 번 제거해 보자.  

 

3개를 제거하고 나니 전깃줄이 꼬이지 않기 위해서는 어떤 원칙을 지켜야 하는지 보이기 시작한다. 

 

그것은 바로 전봇대 A가 전봇대 B로 전사하는 전깃줄은 A의 번호를 기준으로 오름차순이어야 한다. 즉 우리가 구하고자 하는 것은 남아 있는 전깃줄의 번호가 A, B 두 곳 모두에서 증가하게 하는 전깃줄들의 최대 개수이다. 하지만 이것을 어떻게 구할 것인가?

 

먼저 입력받은 A, B 전깃줄 쌍 중에서 A를 기준으로 정렬을 진행한다. 단, 이때 반드시 B도 A의 정렬 위치 변동에 기반해서 B 또한 같이 움직이게 해 준다. 이후 동적 계획법을 이용해서 가장 긴 증가하는 부분 수열을 찾으면 된다. 아직 동적 계획법이 익숙하지 않은 분들은 이 문제를 참고해 주기 바랍니다( 11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net) ).

 

파이썬

import sys;input = sys.stdin.readline
dp=[1]*10;dp[0]=0
n=int(input())
ls=[tuple(map(int, input().split())) for _ in range(n)]
ls.sort()
dp=[1]*n
for i in range(1, n):
    for j in range(i):
        if ls[j][1]<ls[i][1] and dp[j]+1>dp[i]:
            dp[i]=dp[j]+1
print(n-max(dp))

C언어

#include <stdio.h>
#include <stdlib.h>
#define MAX(a, b) (a) > (b) ? (a) : (b)
int partition(int arr[], int arr2[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            temp = arr2[i];
            arr2[i] = arr2[j];
            arr2[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    temp = arr2[i + 1];
    arr2[i + 1] = arr2[high];
    arr2[high] = temp;

    return (i + 1);
}
void quicksort(int arr[], int arr2[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, arr2, low, high);
        quicksort(arr, arr2, low, pi - 1);
        quicksort(arr, arr2, pi + 1, high);
    }
}
int main(){
    int size=0;
    scanf("%d", &size);
    int* left_arr=(int*) malloc(size*sizeof(int));
    int* right_arr=(int*) malloc(size*sizeof(int));
    int* dp=(int*) malloc(size*sizeof(int));
    int a,b;
    for (int i = 0; i < size; ++i) {
        scanf("%d%d",&a,&b );
        left_arr[i]=a;
        right_arr[i]=b;
        dp[i]=1;
    }
    quicksort(left_arr, right_arr, 0, size - 1);
    for (int i = 1; i < size; ++i) {
        for (int j = 0; j < i; ++j) {
            if(right_arr[j]<right_arr[i] && dp[j]+1>dp[i])
                dp[i]=dp[j]+1;
        }
    }
    int max=0;
    for (int i = 0; i < size; ++i)
        max = MAX(max, dp[i]);
    printf("%d", size-max);
    return 0;
}