백준 2352 - 반도체 설계

2352번: 반도체 설계 (acmicpc.net)

2352번: 반도체 설계

 

문제의 핵심은 꼬이는 경우 없이 제일 긴 리스트를 만들어내는 것이다. 제일 긴 리스트를 만들어야 한다는 것에서 '긴 부분 증가수열'을 만들어야하는 것을 알 수 있다. 그렇다면 긴 부분 증가수열(LIS)는 무엇일까?

 

긴 부분 증가 수열이란?

 

예를 들어, 10 20 10 30 40 20 으로 수열이 나열되어 있다고 하면, 긴 부분 증가수열은 10 20 30 40이 되고 길이는 4가 된다.

 

이러한 LIS 리스트를 만드는 것을 생각하면 되는데, 골드 문제 답게 이분탐색을 통해서 문제를 풀어야만 통과가 가능하다.

 

알고리즘

1. 이분탐색 구현

2. 입력받은 port 리스트를 구현

3. Lis 리스트의 초깃값으로 입력받은 port 리스트의 첫 값을 담아준다.

4. port 리스트를 1부터 순회하면서 Lis 리스트의 마지막 값이 port 리스트보다 작으면 Lis 리스트에 담아준다.

5. 만약 Lis 리스트의 마지막 값이 port 리스트보다 크면 이분탐색으로 다시 탐색하고 인덱스를 Lis리스트에서 갱신한다.

 

import sys
input = sys.stdin.readline

def binary_search(arr, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return start

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

Lis = [port[0]]
for i in port[1:]:
    if Lis[-1] < i:
        Lis.append(i)
    else:
        idx = binary_search(Lis, i, 0, len(Lis))
        Lis[idx] = i

print(len(Lis))

 

이렇게 문제 해결이 가능하다. 골드 2라서 상당히 어려울 줄 알았는데 생각보다 Lis 개념과 이분탐색을 잘 사용할 줄만 알면 쉽게 해결이 가능한 문제였다.