[백준알고리즘] 2565번: 전깃줄 -Python

[백준알고리즘] 2565번: 전깃줄 -Python

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

2565번: 전깃줄

20200408

아래부분에 새롭게 푼 코드를 올렸다. 내용은 동일한데 코드가 더 깔끔하다.

---

전깃줄 문제를 풀어봤다. 저번 문제에 이어서 LIS를 응용하는 문제라고 설명이 되어있습니다.

'이게 왜 LIS 문제이냐'라고 한다면, 최소의 선을 없애서 모두 겹치지 않는 선의 상태가 되도록 하라는 것은 모두 겹치지 않는 선의 최대의 집합을 구하면 해당 집합에 들어가지 않는 선이 제거해야할 최소의 선이 되기 때문입니다.

 

처음에 풀어본 방식은 하나씩 전깃줄 쌍 [a, b]를 받을 때마다 추가될 수 있는 부분 수열에 추가하고, 자신이 부분 수열을 하나 더 만들도록 했습니다.

추가될 수 있는 부분 수열을 검사하는 방법은 해당 부분 수열을 반복해서 검사하면서 가로지르는 선이 없는지 확인하였습니다.

가로지르는 두 선의 조건은 임의의 두 선 [a1, b1]와 [a2, b2]가 있을 때 (a1 > a2 && b1 > b2) || (a1 < a2 && b1 < b2)입니다.

즉, 비교 대상의 a1보다 a2가 크면, b1보다 b2도 커야합니다.

하지만 이렇게 했을 때 실패가 떴습니다. 실패가 뜬 이유는 현재 넣으려는 선이 어떤 부분 수열에 들어가게 되는 경우와 들어가지 않는 경우 모두 유지를 해줬어야하기 때문입니다. 이 문제점을 고려하기 위해서 BFS를 사용해서 Branch and Bound를 생각 했습니다. 이것 또한 해봤자 배낭문제에서처럼 시간초과가 뜰 것 같아서 다른 사항을 고려해봤습니다.

 

생각한 방법은 입력을 정렬하는 것입니다. 반드시 입력한 순서대로 줄을 추가할 필요가 없기 때문에 두 전봇대에 이어진 줄들을 한쪽 전봇대를 기준으로 오름차순 정렬을 시도합니다. 그렇게 되면 항상 임의의 두 선 [a1, b1]와 [a2, b2]가 순서대로 정렬이 된 상태라면 항상 a1 < a2이기 때문에 b1 < b2일 경우에만 두 선이 겹치지 않게 됩니다. 그런 경우들의 최대로 구할 수 있는 길이 값을 구하면 됩니다!

 

다시 코드짜고 오겠습니다..

import sys

N = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
arr.sort(key = lambda t: t[0])

lis = [1]
for i in range(1, N):
    # cnt = 1
    # for j in range(i):
    #    if arr[i][1] > arr[j][1]:
    #        cnt += 1
    # lis.append(cnt)
    lis.append(1)
    for j in range(i):
        if arr[i][1] > arr[j][1] and lis[j] + 1 > lis[i]:
            lis[i] = lis[j] + 1

print(N - max(lis))

중간에 주석처리한 부분처럼 했다가 처음했던 방식에서도 처음에 걸렸던 문제를 또 걸려서 생각좀 하라고 놔뒀습니다..ㅎ...

lis값을 비교해야하는 이유는 입력 예시로 보면 정렬했을 때 [2, 2] [3, 9] [4, 1] [6, 4]가 있을 때 lis에는 순서대로 [1, 2, 1]이 있을텐데 여기서 [6, 4]를 추가하게 될 때 lis를 비교하지 않고 주석처리처럼 하게되면 [2, 2]에서도 증가하고 [4, 1]에서도 증가해서 3이 됩니다. 여기서 [2, 2]와 [4, 1]이 서로 겹치기 때문에 [2, 2] [4, 1] [6, 4]로 3의 LIS 집합이 만들어 질 수 없습니다.

 

 

답을 찾는 식은 그나마 나은데, 중간에 뻘짓들을 많이 하는 것 같습니다..

---

20200408

이전에 풀었던 방식과 아이디어는 동일하다. 가장 많이 연결될 수 있는 전깃줄의 갯수를 구한 다음 n에서 빼서 제거해야할 전깃줄 갯수의 최소값을 구했다.

 

전에는 이거 푸는데도 많이 걸렸던것 같은데.. 이렇게 보면 많이 푼 보람이 있는 것 같다.

 

입력된 전깃줄에 대해서 A전봇대의 위치번호를 기준으로 오름차순 정렬을 시킨다.

A전봇대의 위치번호의 오름차순으로 진행을 하며, 연결될 B의 위치번호가 현재 가리키는 위치번호보다 위에 위치한 전깃줄의 최대갯수에 +1을 시켜준다.

n = int(input())
line = [list(map(int, input().split())) for _ in range(n)]
line.sort(key=lambda x: x[0])
dest = [0] * 501

for s, d in line:
    dest[d] = max(dest[:d]) + 1

print(n - max(dest))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다