알고리즘 유형 : DP(Dynamic Programming)
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/2565
import sys
input = sys.stdin.readline
N = int(input())
edge = [list(map(int, input().split())) for _ in range(N)]
# 1 8
# 2 2
# 3 9
# 4 1
# 6 4
# 7 6
# 9 7
# 10 10
# 첫 번째 전봇대 기준 오름차순 정렬
edge = sorted(edge, key = lambda x: x[0])
# LIS
LIS = [1]*N
for idx in range(1, N):
for i in range(idx):
if edge[i][1] < edge[idx][1]:
LIS[idx] = max(LIS[idx], LIS[i] + 1)
print(N - max(LIS))풀이 요약
LIS 알고리즘의 기본 유형 격 문제인데, 어디에 어떻게 활용해야 할지 아이디어가 핵심인 문제였다.
A 전봇대를 기준으로 오름차순 정렬하는 것까진 생각해냈다. 이후에 B 전봇대의 모든 각 값에 대해, 기준 수로 두고 그 밑에 모든 수 중 자기보다 작은 수가 있는 경우, A에서의 값과 B에서의 값의 대소 관계가 다른(=전깃줄 교차) 상태이므로 그 줄을 지우는 방식으로 여러가지 잡다하고 지저분한 코드를 작성하다가 전부 실패했다.
LIS 활용 문제인 건 알고 있었어서, LIS를 어떻게 활용해야할 지 고민했는데 이 것도 잘 안되서 결국 다른 사람 풀이를 참고했다.
B 전봇대에서, "교차된 줄이 없는 그룹"의 상태는 그 값이 오름차순인 상태로 정의할 수 있다. 이 때, 구하고자 하는 것은 전깃줄을 없애는 최소 개수인데, 이는 곧 교차되지 않은 상태의 전깃줄을 최대한 많이 남기는 것과 같은 경우이다. 그리고 이 말은 "교차된 줄이 없는 그룹"이 최대, 즉 오름차순인 그룹의 최대, LIS를 구하는 것과 같은 말이다. 요게 내가 생각 못한 핵심! LIS를 구하고, N - LIS를 출력하면 통과
-
A 전봇대와 B 전봇대를 잇는 전깃줄 edge 정보를 2차원 배열로 저장
-
A 전봇대 기준(임의의 수 k에 대해 edge[k][0]) 오름차순 정렬(B 전봇대 기준으로 해도 됨)
-
B 전봇대 값에 대해 LIS 구하기
-
N - LIS 출력(전체 전깃줄 - 교차 없는 전깃줄 그룹 중 최대 길이)
배운 점, 부족했던 점
-
B 전봇대 값에 대해 교차 전깃줄을 없애는 최소 개수 = N - LIS(교차 없는 전깃줄 그룹 최대 길이) 이 아이디어를 떠올려내지 못한 것
-
sorted()로 리스트 정렬할 때, 정렬 키 인자로 람다식 쓰는 방법 자세하게 기억이 안나서 검색해 봄.
lambda x: x[0] (x는 리스트의 원소, 콜론 이후 식은 x에 대한 다양한 형태의 표현식)
