백준 No.2565 - 전깃줄

출처:https://www.acmicpc.net/submit/2565

 

문제

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

 

입력

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.

 

출력

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

 

 

단계별 알고리즘 학습을 하는 도중 만나게 된 전깃줄 문제..

카테고리는 동적프로그래밍(Dynamic Programming)에 속하는 문제이다.

DP에서는 점화식을 세우는게 기본소양이자 가장 중요한 부분인듯한데, 나의 머리로는 도저히 점화식을 떠올릴 수 없는 경우가 너무 많다

 

가장 먼저 생각했던 방법은 두 line을 비교하여 교차한다면 dp배열에 1씩 더해주는 방식을 떠올렸다.

2중loop를 사용하긴 하지만 n의 최대값이 100이기 때문에 시간 복잡도는 오래 걸리지 않을터

 

n = int(input())

lines = []

for _ in range(n):

    lines.append(list(map(int, input().split())))

dp = [0] * n

result = 0

for i in range(n-1):

    for j in range(i+1, n):

        x, y = lines[i]

        a, b = lines[j]

        if (x > a and y < b) or (x < a and y > b):

            dp[i] += 1



for i in dp:

    if i > 0:

        result += 1

 

하지만 여지없이 틀리고 말았다...

이후로 순회방향을 바꿔보기도 하고 다양하게 시도해보았지만 "틀렸습니다"를 굉장히 많이 마주했다.

결국 집단지성(?)을 발휘하기 위해 구글링을 시도했다.

 

역시 구글링은 나를 실망시키지 않았다.

이 문제를 게시한 분들도 대다수 발상의 전환이 중요하다는 것을 깨달았다고 한다.

구현은 생각보다 간단했다. 다만 구현할 '무언가'를 찾아내는 것이 어려울 뿐.

 

문제에서 요구한 최소한의 제거가 아닌, 최대한의 증설로 접근하는 것.

한 쪽을 기준으로 sorting을 한 뒤에 다른 한 쪽에서 최대증가수열을 구하는 것이 핵심이었다.

어찌 생각해보면 당연한 것인데 왜 떠올리지 못했을까라는 생각도 든다.

 

최종적인 답안 코드는 다음과 같다.

 

n = int(input())
lines = []
for _ in range(n):
    lines.append(list(map(int, input().split())))
dp = [1] * n

lines.sort()

for i in range(n):
    for j in range(i-1, -1, -1):
        if lines[i][1] > lines[j][1]:
            dp[i] = max(dp[i], dp[j]+1)
print(n-max(dp))

 

처음 구상했던 코드보다 훨씬 간결하고 정확한 답을 도출할 수 있었다.

 

발상의 전환, 언제나 기억하자!