[ 백준 / 골드2 / 파이썬 Python ] 1365번 - 꼬인 전깃줄

링크 : https://www.acmicpc.net/problem/1365

1365번: 꼬인 전깃줄

 

코드

---

import bisect
n = int(input())
arr = list(map(int,input().split()))
stack = []

for x in arr:
    if not stack or x > stack[-1]:
        stack.append(x)
        continue
    loc = bisect.bisect_left(stack,x)
    stack[loc] = x

print(n-len(stack))

 

풀이

---

처음 보면 어려울 수 있으나 LIS(가장 긴 증가하는 부분수열) 알고리즘을 공부했다면 쉽게 해결할 수 있는 문제이다.

 

이 문제의 핵심은 "어떤 전깃줄을 삭제하는냐"가 아니라 "몇 개의 전깃줄을 삭제하느냐"이다. 만약에 어떤 전깃줄을 삭제해야하는지 찾아야 했다면 DP를 사용해야 할 것이다. 하지만 개수만을 따진다면 이분탐색을 이용한 LCS를 통해 간단하고 빠르게 해결 가능하다.

 

문제를 해결하는 방법은 다음과 같다.

1. stack 배열이 비었거나 stack배열의 마지막 원소보다 큰 수라면 맨 마지막에 집어넣는다.
2. 그렇지 않다면 이분탐색으로 기존의 stack배열 중 현재 값이 들어갈 위치를 찾아 바꿔준다.

가장 긴 증가하는 부분수열의 말 그대로 1번은 이해하기 쉬운 방법이다. 하지만 2번은 살짝 어려울 수 있다.

 

그래서 예시를 하나 들어보자. 

예를 들어, [3,6,1,7,2,3] 이라는 배열이 있을 때, 순서대로 어떤 방식으로 LCS의 개수를 구하는지 보겠다.

• 입력 = 3 | stack = [] : stack이 비어있기 때문에 먼저 수를 집어넣어야 하므로 3을 집어넣는다.
• 입력 = 6 | stack = [3] : stack이 비어있지는 않지만 가장 마지막 수 3보다 크므로 6을 집어넣는다.
• 입력 = 1 | stack = [3,6] : stack이 비어있지도 않고 가장 마지막 수보다도 작다. 따라서 이분탐색을 통해 자기 자리를 찾아준다.
  • 이 때, 1은 3,6보다 작기 때문에 bisect_left에 의해 0을 리턴한다. 따라서 0번자리에 3을 1로 바꾸어 준다.
  • 이게 가능한 이유는 개수만 센다는 가정하에 LCS란 가장 뒤의 수보다 큰 수만 찾으면 되기 때문이다. 결국은 증가하는 부분수열이기 때문에 가장 뒤 원소보다 클 때만 길이가 증가하고 나머지는 자기 자리만 찾아주면 된다.
• 입력 = 7 | stack = [1,6] : 두 번째 경우와 마찬가지로 맨 뒤에 넣어준다.
• 입력 = 2 | stack = [1,6,7] : 세 번째 경우와 마찬가지로 6을 2로 바꿔준다.
• 입력 = 3 | stack = [1,3,7] : 맨 처음 입력도 3이었지만 삭제된 것에 반해 다시 들어와준 모습이다.

LCS를 구한다면 정답은 [3,6,7]이나 [1,2,3]이 되겠지만 우리는 원소의 종류는 다르지만 개수는 정확한 답을 구할 수 있었다.