[Python] 2565 - 전깃줄 (골드5)

1. 문제 설명

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

2565번: 전깃줄

 

---

2. 아이디어

그렇게 쉬운 문제는 아니었는데, 그 당시에 dp 문제만 주구장창 풀어서 금방 해결했었다.

어차피 전봇대 최대 개수는 500개 이하이므로 pole은 연결된 전봇대 정보 외엔 모두 False로 할당하고

cache는 그 중에서도 유효한 전봇대를 체크해줄 리스트로써 0으로 초기화 한다.

 

유효한 전봇대라니? 대체 그걸 어떻게 판단한다는 것인가.

이 문제가 전봇대로 나와서 그렇지 조금만 고민해보면 완전히 다른 문제로 접근이 가능하다.

 

예를 들어, 1~4번까지 전봇대가 B의 [4, 1, 2, 3] 전봇대와 연결되어 있다고 하자.

최소로 끊는 전깃줄은 A의 1번을 선택하면 됨을 알 수 있다.

그럼 남는 수가 [1, 2, 3]인데 이것만으로는 아직 패턴이 보이지 않았을 수 있다.

 

이번에는 순서대로 B의 [8, 2, 9, 1, 4, 6, 7, 10] 전봇대와 연결되어 있는 A전봇대가 있다고 가정할 때,

최소로 전깃줄을 끊은 후에 연결된 B의 전봇대는 [2, 4, 6, 7, 10]이다.

이전과 이번의 공통점을 찾았는가? 바로 결과가 가장 긴 증가수열이라는 것이다.

 

가장 긴 증가하는 부분 수열(BOJ-11053) 문제를 풀어본다면

이 문제와 매우 흡사한 코드로 해결할 수 있음을 알 수 있다.

 

현재 A의 전봇대와 이전의 모든 A 전봇대를 비교했을 때 교차하는 전선이 존재하고,

cache[현재] < cache[이전] + 1 이 성립한다면 이 구간은 감소수열이므로

이전 전봇대가 유효하지 않다고 판단하고 제거한다.

 

잘 이해가 가지 않는다면 가장 긴 증가하는 부분 수열 문제를 풀어보는 것이 좋다.

 

---

3. 코드

import sys
input = sys.stdin.readline

def solution():
    n = int(input())
    pole = [False]*501
    for _ in range(n):
        a, b = map(int, input().split())
        pole[a] = b
    cache = [1]*501

    for i in range(1, 501):
        if not pole[i]:
            continue
        for j in range(1, i):
            if not pole[j]:
                continue
            if pole[i] > pole[j] and cache[i] < cache[j] + 1:
                cache[i] = cache[j] + 1
    print(n - max(cache))

solution()