[백준] 2565 전깃줄 python

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

2565번: 전깃줄

 

import sys; input = sys.stdin.readline
def checkCross(cables, ignore_idx_set):
    cross = [0 for _ in range(len(cables))]
    for i in range(len(cables)):
        if i in ignore_idx_set: continue
        s1, e1 = cables[i]

        for j in range(i + 1, len(cables)):
            if j in ignore_idx_set: continue
            s2, e2 = cables[j]
            if (s1 < s2 and e1 > e2) or (s1 > s2 and e1 < e2):
                cross[i] += 1
                cross[j] += 1

    return cross


N = int(input())
cables = [tuple(map(int, input().split())) for _ in range(N)]
# cables = [(1, 8), (3, 9), (2, 2), (4, 1), (6, 4), (10, 10), (9, 7), (7, 6)]
answer = 0
ignore = set()  # store cable index to ignore

while True:
    # 1 교차점 확인
    crossList = checkCross(cables, ignore)
    # 2 교차점이 하나도 없는 경우 탈출
    if sum(crossList) == 0:
        print(ignore)
        break
    # 3 교차점이 가장 많은 점 제거
    ignore.add(crossList.index(max(crossList)))
    answer += 1

print(answer)

교차점이 가장 많은 전기줄을 하나씩 제거하는 방식으로 진행하였다. 사실 제출하기전에도 정답이 되지 않을걸 알았는데, 교차점이 같은 전기줄이 많은 경우에 먼저 제거하는것에 따라 답이 바뀔수 있다고 생각이 들었다. 

제출했을때도 틀렸다는 것을 알 수 있었다.

---

import sys; input = sys.stdin.readline

N = int(input())
cables = [tuple(map(int, input().split())) for _ in range(N)]
cables.sort(key=lambda x: x[0])

# 두번째 전봇대에서 LIS 구하기(DP)
def binary_search(arr, l, r, target):
    while l < r:
        mid = (l + r) // 2
        if arr[mid] < target:
            l = mid + 1
        else:
            r = mid
    return r

new_list = [0] + [e for s, e in cables]
d = []
for idx in range(1, N + 1):
    if not d or new_list[idx] > d[-1]:
        d.append(new_list[idx])
    else:
        tmp_i = binary_search(d, 0, len(d), new_list[idx])
        d[tmp_i] = new_list[idx]

print(N - len(d))

두번째 접근은 첫번째 전봇대에서 오름차순 정렬을 한뒤 두번째 전봇대에서 가장 길게 만들수 있는 증가부분 수열을 찾는 것이다. 내가 생각한 알고리즘은 아니고 한시간정도 머리를 싸매고 있다가 게시판을 찾아서 알게되었다.

LIS 에 대해선 아래 블로그가 자세히 알려줄것이다.

https://velog.io/@seho100/%EC%B5%9C%EA%B0%95-%EC%A6%9D%EA%B0%80-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4LIS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98