2565

날짜 : 2023. 06. 09

사용 언어 : python

 

문제

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

 

 

코드

import sys

n = int(sys.stdin.readline())
line = list()
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())  # 전깃줄 입력
    line.append([a, b])
line.sort()  # a 기준으로 정렬
# print(line)
dp = [1] * n
for i in range(1, n):
    for j in range(i):
        if line[i][1] > line[j][1] and dp[i] <= dp[j]:  # 증가하는 가장 큰 부분수열 구하기
            dp[i] = dp[j] + 1
# print(dp)
print(n - max(dp))

 

 

풀이

- 기본적으로 전깃줄일 겹치는 경우는 a1-b1, a2-b2가 있고 a1 < a2일 때, b1 > b2인 경우에 발생한다.

- 그렇기 때문에 반대로 전깃줄들을 a에 대하여 오름차순으로 정렬한 후, b에 대하여 메모이제이션을 실행한다.

- 즉, b에 대하여 증가하는 가장 큰 부분수열을 구한 후, 그 값을 전체에서 뺀다면 겹치지 않도록 하기 위한 최소한의 전깃줄 삭제 개수를 구할 수 있다.

 

 

알게된 점

- A에 대하여 정렬하고,  a1-b1, a2-b2가 있고 a1 < a2일 때, b1 > b2인 경우에 발생한다는 것까지는 도출할 수 있었지만, 맨 처음 (1, 8) 이후 하위 라인들의 케이스도 모두 구해야 한다는 생각에 정체했었다.

- 이후 풀이를 찾아보았고 앞서 풀었던 증가하는 가장 긴 수열 문제와 유사하다는 것을 알 수 있었고, 그 풀이도 다시 확인하면서 dp를 활용하는 방식을 리뷰할 수 있었다.

- 추가로 증가하는 가장 긴 수열, 즉 LIS 알고리즘이 정리되어 존재하는 것도 공부하게 되는 계기가 되었다.

 

 

참고 사이트

- https://chanhuiseok.github.io/posts/algo-49/

알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘