[BOJ] 2352: 반도체 설계

문제: https://www.acmicpc.net/problem/2352

해법

입력으로 들어오는 숫자들을 다음과 같은 로직으로 stack에 넣는다.

1. list의 top에 있는 숫자보다 현재 입력으로 들어온 숫자가 더 크다면 그대로 stack에 넣는다.
2. list의 top에 있는 숫자보다 현재 입력으로 들어온 숫자가 더 작다면 list에서 이분 탐색으로 현재 입력된 숫자가 list의 sort를 깨트리지 않고 들어갈 수 있는 index를 찾은 뒤, 해당 index에 있던 숫자와 교환해준다.

LIS 문제와 해법이 정확하게 똑같다.

위 예시처럼 숫자가 더 작은 포트를 연결하는 것이 이득인 경우가 있는 한편,

위 예시처럼 숫자가 더 작은 포트랑 연결되는 선이 있어도 연결하는 것이 손해인 경우도 있기에 LIS 문제인지 헷갈리게 한다.

하지만 2번째 케이스에 더 작은 포트랑 연결된 선이 실제로 필요하냐의 여부와 별개로, 문제에서는 최종적으로 남은 선의 개수만을 요구하기에, LIS처럼 풀어도 해결할 수 있다. 더 작은 포트랑 연결된 선을 이용하는 것이 최종적으로 보았을 때 이득이라면 넣어두는 것이 맞고, 이득이 아니더라도 숫자 한 개를 빼고 숫자 한 개를 넣는 것이기에 list의 길이에는 차이가 발생하지 않는다.

코드

from bisect import bisect_left

n = int(input())
A = list(map(int, input().split()))

numbers = [-1e9 - 1]

for i in range(n):
    if A[i] > stack[-1]:
        numbers.append(A[i])
    else:
        index = bisect_left(numbers, A[i])
        numbers[index] = A[i]

print(len(stack) - 1)