[baekjoon] 백준 2565번(파이썬): 전깃줄

문제

2565번: 전깃줄

알고리즘

- 0번째 idx를 기준으로 오름차순 정렬을 한다.

- 정렬된 전깃줄에 가장 길게 증가하는 부분 수열을 찾는다. 

- 이중 반복문을 통해 n번의 수까지 증가하는 길이를 구한다.

- 길이를 구할 때 i번의 수와 그전에 수들을 비교한다.

- 0번째 idx를 기준으로 오름차순 정렬을 했기 때문에 1번째 idx를 기준으로 수들을 비교한다.

- 이때 가장 길게 증가하는 부분 수열이 겹치지 않는 전깃줄이므로 전체에서 빼준 값을 출력한다.

코드

import sys


n = int(sys.stdin.readline())
m = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
m.sort(key=lambda x: x[0]) # 0번째 idx를 기준으로 오름차순 정렬
dp = [0] * n

# 반복문을 통해 가장 길게 증가하는 부분 수열을 찾는다.
for i in range(n):
    result_max = 0
    for j in range(i):
        # 0번째 idx를 기준으로 오름차순 정렬을 했기 때문에
        # 1번째 idx를 기준으로 증가하는 부분 수열을 찾는다.
        if m[i][1] > m[j][1]:
            if result_max < dp[j]:
                result_max = dp[j]

    dp[i] = result_max + 1

print(n - max(dp))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법