백준 온라인 저지, 이진탐색 / 1365번: 꼬인전깃줄 (파이썬 / 백준 골드문제)

문제

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

문제 정의

공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 아래와 같이 두 줄로 늘어서 있다. 그리고 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있다. 어떤 전봇대도 두 개 이상의 다른 전봇대와 연결되어 있지는 않다.

문제는 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있다는 점이다. 꼬여있는 전깃줄은 화재를 유발할 가능성이 있기 때문에 유스타운 시의 시장 임한수는 전격적으로 이 문제를 해결하기로 했다.
임한수는 꼬여 있는 전깃줄 중 몇 개를 적절히 잘라 내어 이 문제를 해결하기로 했다. 하지만 이미 설치해 놓은 전선이 아깝기 때문에 잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다.
유스타운 시의 시장 임한수를 도와 잘라내야 할 전선의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 몇 번 전봇대인지를 나타낸다.

출력

전선이 꼬이지 않으려면 최소 몇 개의 전선을 잘라내야 하는 지를 첫째 줄에 출력한다.

예제 입력 1

4
2 3 4 1

예제 출력 1

1

접근 방법

- 증가하는 부분수열로 로직을 작성한 뒤, N에서 가장 큰 값을 빼준다.
- 현재 탐색하는 수보다 앞에 있는 수 중 작은 수의 개수 + 1을 인덱스로 하는 리스트의 값에 작은 값을 입력한다.

코드

# https://www.acmicpc.net/status?user_id=gksqlsl11&problem_id=1365&from_mine=1
# 접근 방법
# 증가하는 부분수열로 로직을 작성한 뒤, N에서 가장 큰 값을 빼준다.
# 현재 탐색하는 수보다 앞에 있는 수 중 작은 수의 개수 + 1을 인덱스로 하는 리스트의 값에 작은 값을 입력한다.
n = int(input())
array = list(map(int, input().split()))
d = [n+1] * (n+1) # dp 테이블 초기화 / 인덱스 = 부분수열의 개수, 값 = 그 개수에 해당하는 전봇대 번호 중 더 작은 수 
d[1] = array[0]
for x in array[1:]:
    # 이진탐색 진행
    start = 1
    end = n + 1
    index = 0
    while start <= end:
        mid = (start + end) // 2
        if d[mid] < x: # 탐색 중인 수가 mid개의 부분수열을 가진 어떤 수보다 크다면
            index = max(index, mid)
            start = mid + 1
        else:
            end = mid - 1
    # 현재 찾은 부분수열의 개수 인덱스의 값에 이를 저장(항상 탐색 중인 수는 다음 인덱스보다 작을 수밖에 없음)
    d[index + 1] = x
    # print(d)
for i in range(1, n + 1):
    if d[i] == n + 1: # i : 부분 수열의 개수 + 1
        break
print(n - (i - 1)) # 현재 주어진 전봇대의 수 - 부분 수열의 개수