[백준] 2565번 전깃줄

문제링크: https://www.acmicpc.net/problem/2565

아이디어

i < j 라면, A의 i번이 연결되어 있는 B의 위치 < A의 j번이 연결되어 있는 B의 위치를 만족해야 한다.
1. 전깃줄의 연결관계를 A를 기준으로 정렬
2. A의 i번째 위치의 전깃줄이 존재하는 경우, 최대로 연결될 수 있는 전깃줄의 갯수 = i번 이하의 위치에서 최대로 연결될 수 있는 전깃줄의 갯수

코드

import sys
input = sys.stdin.readline


class Wires:
    def __init__(self, total_wires: int = 0, wires=None) -> None:
        if total_wires > 0 and wires == None:
            raise Exception(
                f"{self.__class__} {sys._getframe().f_code.co_name}: there is no wire")

        self.total_wires = total_wires
        self.wires = wires

    def remove_wire(self):
        remained_wires = [1] * self.total_wires
        if self.wires == None:
            raise Exception(
                f"{self.__class__} {sys._getframe().f_code.co_name}: there is no wire")

        ordered_wires = sorted(self.wires)
        for i in range(self.total_wires):
            for j in range(i):
                if ordered_wires[j][1] < ordered_wires[i][1]:
                    remained_wires[i] = max(
                        remained_wires[i], remained_wires[j]+1)
        return self.total_wires - max(remained_wires)


def init_data():
    total_wires = int(input())
    wires = [list(map(int, input().split())) for _ in range(total_wires)]

    return Wires(total_wires, wires)


if __name__ == "__main__":
    wires = init_data()
    print(wires.remove_wire())

결과