백준 2565번 - 전깃줄

전깃줄 문제 바로 가기

풀이 날짜: 2026-01-13

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline

n = int(input())
data = []
for _ in range(n):
    data.append(list(map(int, input().split())))
data.sort()

b = [x[1] for x in data]

dp = [1]*n

for i in range(n):
    for j in range(i):
        if b[j] < b[i]:
            dp[i] = max(dp[i], dp[j]+1)

lis = max(dp)
print(n-lis)

문제 핵심 요약:

전깃줄이 교차하지 않게 일부를 제거하라는 문제라서 처음에는 “교차하는 것만 하나씩 제거하면 되지 않나?”라고 생각했다. 하지만 전깃줄의 개수가 늘어나면 어떤 것을 먼저 제거해야 하는지 판단하기가 어려워지고, 단순한 그리디 방식으로는 모든 경우를 보장할 수 없다는 것을 느꼈다. 이 문제는 결국 어떤 전깃줄들을 남길지 선택하는 문제라는 점에서 DP 관점으로 접근해야 했다.

교차 조건 파악하기

전깃줄 두 개 (A1, B1), (A2, B2)가 교차하는 조건은 A1 < A2 인데 B1 > B2 인 경우다. 이 조건을 보고 깨달은 점은, A 쪽의 순서와 B 쪽의 순서가 서로 반대가 될 때 교차가 발생한다는 것이다. 따라서 A를 기준으로 정렬해 두면, 이후에는 B 값이 증가하는지 감소하는지만 보면 교차 여부를 판단할 수 있다.

DFS + DP(메모이제이션)

각 칸에서 더 큰 값으로만 이동하므로 경로는 항상 증가 방향이다. 즉 재귀로 ‘최대로 뻗는 길이’를 계산하면 된다. 단 모든 칸에서 DFS를 하면 중복 계산이 발생하기 때문에, 이미 계산한 칸의 결과를 dp에 저장해두고 재사용하는 ‘메모이제이션’이 필요했다.

A를 정렬한 뒤 B만 보는 이유

전깃줄을 A 기준으로 정렬하면 A는 항상 증가하는 순서가 된다. 이 상태에서는 A 값은 더 이상 비교할 필요가 없고, 교차 여부는 전적으로 B의 증가/감소에 의해 결정된다. 그래서 (A, B) 전체를 볼 필요 없이, B 값들만 뽑아 하나의 수열로 만든 뒤 이 수열에서 문제를 해결하게 된다.

dp 배열

dp[i] = i번째 전깃줄을 마지막으로 사용했을 때, 만들 수 있는 가장 긴 증가 부분 수열의 길이

구현 과정에서 겪은 어려움

이중 반복문 구현

바깥 반복문 i는 “이번에 마지막으로 사용할 전깃줄”을 의미한다. 안쪽 반복문 j는 i보다 앞에 있는 전깃줄들 중, i 앞에 올 수 있는 후보들을 전부 검사하는 과정이다. 이때 b[j] < b[i]라는 조건은, j 뒤에 i를 붙여도 전깃줄이 교차하지 않는지를 확인하는 조건이다.

최종 답이 n - LIS 인 이유

dp 배열에서 가장 큰 값은, 교차 없이 남길 수 있는 전깃줄의 최대 개수를 의미한다. 전체 전깃줄 개수가 n개이므로, 나머지는 모두 제거해야 한다. 따라서 이 문제의 정답은 n - LIS가 된다.

Vienna sausage