백준 2565번: 전깃줄 (Python)

접근

동적 계획법(Dynamic Programing, DP) 문제 분류에 가장 긴 증가하는 부분 수열과 같은 문제였다.

2021.03.28 - [코딩/백준 (Python)] - 백준 11053번: 가장 긴 증가하는 부분 수열 (Python)

백준 11053번: 가장 긴 증가하는 부분 수열 (Python)

입력되는 케이블 연결 x, y 값을 A[x] = y 형태로 저장하여 리스트 A를 작성하고 이를 탐색한다. 케이블이 꼬이지 않은 상태이기 위해서는 각 A[i]에 해당하는 값이 i가 증가할수록 증가해야만 한다. (증가하는 부분 수열) 다만 전체 케이블 개수 n에서 가장 긴 증가하는 부분 수열의 길이 max(dp)의 값을 뺀 값이 제거해야하는 전깃줄의 수가 된다.

코드

import sys

n = int(sys.stdin.readline())
A = [0 for _ in range(502)]
cross = A[:]
for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    A[a] = b
dp = A[:]
for i in range(1, len(A)):
    maximum = -1
    for j in range(i):
        if A[j] < A[i]:
            if dp[j] >= maximum:
                maximum = dp[j]
    dp[i] = maximum + 1
print(n - max(dp))

더 생각해 볼 것?

문제 설명에서 LIS 문제임을 알고 나서야 풀이 방법을 생각해낼 수 있었다는 점이 개인적으로 아쉬운 문제였다.