2565번 전깃줄

deepvine·2021년 5월 25일
0

알고리즘

목록 보기
1/2

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

재밌는 LIS 유형 문제가 있어 정리해보았다.

먼저 아래와 같이 입력이 주어진다고 하면

1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

아래와 같은 모양으로 전깃줄이 엉켜 있는 것이다

근데 여기서 (6, 4)로 이어져 있는 전깃줄의 기준에서 보면

(6, 4)까지 있을 때 엉켜 있지 않은 전깃줄의 최대 개수는 아래와 같이 2가지 경우의 수를 생각할 수 있고

결과적으로 (6, 4)까지 전깃줄에서 볼 때 최대 전깃줄의 개수는 2라는 것을 알 수 있다

(7, 6) 전깃줄의 기준에서 봤을 때 아래와 같이 2가지의 경우의 수를 생각해 볼 수 있고

이는 방금 위에서 본 (6, 4) 전깃줄의 최대값에 + 1((7, 6) 포함) 인 값으로 말할 수 있다

따라서 이를 일반화해 보면 현재까지(ii) 전깃줄로 구성된 전깃줄의 최대 개수는 이전 전깃줄(jj) 구성의 최개 개수 + 1 로 일반화가 가능하다

dp[i]=max(dp[i],dp[j]+1)dp[i] = \max(dp[i], \quad dp[j] + 1)

따라서 문제는 전깃줄이 최대로 엉키지 않도록 하는 잘라야할 전깃줄의 개수이므로 전체 전깃줄 셋의 개수(NN)에서 빼주면 된다

Nmax(dp)N - \max(dp)

이를 파이썬 코드로 표현하면 아래와 같다

import sys

N = int(input())
v = []
for i in range(N):
    a = list(map(int, input().split()))
    v.append(a)
v.sort()

dp = [1] * (N)

for i in range(1, N):
    for j in range(0, i):
        if (v[i][0] > v[j][0] and v[i][1] > v[j][1]) or \
            (v[i][0] < v[j][0] and v[i][1] < v[j][1]):
            dp[i] = max(dp[i], dp[j] + 1)

print(N - max(dp))
profile
변화된 그리고 여전한

0개의 댓글