백준 2565) 전깃줄 (골드.5)

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

2565번: 전깃줄

문제

 

 

서로 겹치지 않도록 전깃줄을 위치하기 위해서 제거해야하는 전깃줄의 갯수를 구하는 문제이다. 

 

처음에는 순서와 상관없이 서로 교차하는 전깃줄의 교차여부를 2차원 배열에 담고, 교차하는 부분이 있는 전깃줄을 모두 제거해버리는 코드를 작성했었다. 그런데 이 코드는 중복해서 교차하는 전깃줄을 제거했을 때의 반영을 전혀하지 못하기 때문에 당연히 실패하였다😭

n = int(input())
rope = []
dp = [[0]*n for _ in range(n)]
answer = 0
for _ in range(n):
    a, b = map(int, input().split())
    rope.append((a, b))

for i in range(n-1):
    for j in range(i+1, n):
        a, b = rope[i]
        c, d = rope[j]
        if a>c and b<d or a<c and b>d:
            dp[i][j] = 1

for i in range(n):
    if max(dp[i])>0:
        answer+=1
print(answer)

 

 

 

다른 풀이를 보고 다시 생각해서 최장 증가 수열 부분(LIS)을 구하고 이 부분은 서로 겹치지 않게 위치한 전깃줄의 갯수이므로 이를 이용해서 모든 전깃줄의 갯수 (n) - 겹치지 않은 전깃줄의 갯수 = 겹치는 전깃줄 의 갯수를 구하도록 하였다.  

n = int(input())
rope = []
dp = [1]*n
for _ in range(n):
    a, b = map(int, input().split())
    rope.append((a, b))
rope.sort()

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