[BOJ] 2565번: 전깃줄

https://www.acmicpc.net/

문제풀이

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

2565번: 전깃줄

우선 전깃줄을 하나씩 보면서 그때까지 가질 수 있는 최대 전깃줄 개수를 구해야 한다는 것을 제일 먼저 생각해야한다. 그렇다면 최대 전깃줄 개수를 어떻게 구할 수 있을까를 생각해야한다. 두개의 전깃줄이 있을 때 A와 B에서의 위치를 (a1, b1), (a2, b2)라고 한다면 전깃줄이 교차되지 않기 위해서는 a1 < a2 and b1 < b2 이거나 a1 > a2 and b1 > b2 여야한다. 즉 대소관계가 분명해야 한다는 것! 이것에 기반을 두고 다이나믹 프로그래밍을 통해 구할 수 있다. 우리가 저장할 값은 i 번째까지의 전깃줄 중에서 몇개의 교차하지 않는 전깃줄이 존재하는가 이다. 이 방식을 통해 구할 수 있다.

 

Python3

import sys
n = int(sys.stdin.readline())
line = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [0]*n
line.sort()
print(line)
for i in range(n):
    for j in range(i):
        a1, b1 = line[i]
        a2, b2 = line[j]
        if a1 > a2 and b1 > b2 and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
print(dp)
print(n - max(dp))

전깃줄 위치를 튜플로서 입력받았다. 이후 n개의 dp 배열을 만들었다. 이 배열은 n번째 일 때까지 중에서 최대 전깃줄 개수이다. 여기서 중요한 점은 전깃줄을 정렬해야한다는 것이다. 입력받는 전깃줄은 마구잡이로 입력되기 때문에 내가 작성한 코드에서는 예외가 발생한다. 

주어진 예제처럼 전깃줄이 주어진다고 해보자.

1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

10, 10이까지는 잘 진행되지만 이후 9, 7을 보았을 때 문제가 발생한다. 서로 겹치지 않는 전깃줄이지만 내 코드에서는 9, 7이 10, 10보다 커야만 겹치지 않는다고 생각하기 때문이다. 따라서 A 위치에 대한 정렬이 필요하다. 한 위치당 하나의 전깃줄만 존재하기 때문에 B위치에 대해서는 고려할 필요가 없다.

다 구하고 나면 우리가 구한 것은 최대 전깃줄 개수이기때문에 총 전깃줄 개수에서 이 값을 빼서 없애야할 전깃줄의 개수를 구하면 된다.