[백준 #2565 파이썬] 전깃줄

생각은 맞았지만 생각을 전개하는 방식에 문제가 있었다.

이 문제를 다시 푸는 경우에는 증가하는 수열에 대한 개념을 먼저 알고 푸는 것이 도움이 될 듯하다.

 

생각

1. 교차하는 방법을 정리한다.

2. 순서대로 정렬하여 교차가 발생하는 지점을 센다.

 

일단은 생각대로는 풀었지만, 그 생각이 결국 수정이 필요한 생각이었다.

 

구현 (수정이 필요했음)

1. 최대 번호에 맞는 배열 크기를 초기화 한다.

2. 전깃줄을 정렬한다.

3. 시작과 끝 지점을 저장해 정렬한다. 

이때 시작지점이 기존 값보다 크면서(작으면서) 도착 지점이 기존 도착 값보다 작으면(크면) 교차가 발생한다.

이때, 기존 값에 count 1을 더해준다. 그렇게 나온 제거가 필요한 위치를 세어준다.

여러 반레도 맞추고 예제도 맞출 수 있었지만 9%만 달성하고 틀리게 되었다...

생각해보면 공간 낭비도 있었고 dp의 요소를 충분히 고려하지 못한 풀이였다고 생각한다. 

 

아래는 틀린 풀이

n = int(input())
l =  []
start = []
end = []
dp = [0] * (501)

for i in range(n):
    l.append(list(map(int,input().split())))
l.sort(key = lambda x:x[0])

for x,y in l:
    start.append(x)
    end.append(y)

for x,y in l:
    cnt = 0 
    for i,j in zip(start,end):
        if i < x and j > y:
            dp[j] += 1

ans = 0
for i in range(len(dp)):
    if dp[i] != 0:
        ans += 1
print(ans)

정답 풀이

가장 긴 증가하는 부분 수열을 생각해보면 좋다. 사실 이걸 생각하기에는 dp에 대한 경험을 조금 더 쌓아야 가능할 것 같다고 생각한다.

부분 수열 만큼 비교를 반복하면서 값을 갱신해나가는 방법을 그대로 사용하면 교차해야 하는 전깃줄의 개수를 쉽게 구할 수 있다!

dp의 가장 기본이 되는 문제이니 다시 한번 살펴보자

n = int(input())
ㅣ = sorted([list(map(int, input().split())) for _ in range(n)])

dp = [1] * n
for i in range(1,n):
    for j in range(i):
        if ㅣ[i][1] > ㅣ[j][1]:
            dp[i] = max(dp[i], dp[j] + 1)

print(n - max(dp))