백준 2565번 : 전깃줄

내 코드

import sys
input = sys.stdin.readline

n = int(input())
table = {}
data = [[] for _ in range(101)]

for _ in range(n):
    a, b = map(int, input().split())
    table[a] = b
    for t in table.keys():
        if t == a:
            continue
        if (a-t) * (table[a] - table[t]) < 0:
            data[a].append(t)
            data[t].append(a)

count = 0
while True:
    tmp = 0
    res = 0
    for i in range(len(data)):
        if len(data[i]) > tmp:
            res = i
            tmp = len(data[i])
    if tmp == 0:
        break
    for d in data[res]:
        data[d].remove(res)
    data[res] = []
    count += 1

print(count)

런타임에러가 났는데 왜 났는지 알아내지 못함. 결국 포기하고 다른 분들 풀이를 봄.
lis 이용해야 한다는 것을 깨닫고 다시 풀기 시작....

import sys
input = sys.stdin.readline


def lis(arr, n):
    rst = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                rst[i] = max(rst[i], rst[j] + 1)
    return max(rst)

def solve():
    n = int(input())
    arr = []
    for _ in range(n):
        a, b = map(int, input().split())
        arr.append((a, b))
    arr.sort(key = lambda x : x[0])
    l = []
    for a, b in arr:
        l.append(b)
    print(n - lis(l, n))

solve()

DP 문제 중 하나로, 최대 증가 부분 수열 문제라고 한다. 들어본 적도 없었던 내 입장에선 10시간 고민했어도 이런 방식으로는 접근하지 못했을 것 같아서 정답을 보길 잘했다는 생각이 들었다.

A B -> lis
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

데이터를 받고 A부분을 우선 정렬시킨 후 B에서 최대 증가 부분 수열을 찾는 문제였다...