[백준] 12014 주식

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

 

전형적인 LIS + binary search 문제이다.

 

최장 증가 부분 수열이라고 하는 LIS는 DP를 통해 O(N^2)로 풀거나, 이진탐색으로 O(nlogn)으로 풀 수 있다.

 

가장 긴 증가하는 부분 수열을 알아내는 방법에 이진 탐색을 쓰는 이유는 찾고자 하는 LIS 배열이 정렬되어 있기 때문에 logN의 시간복잡도로 있어야 할 인덱스를 알아낼 수 있기 때문이다. 무슨 말이냐면 예시로

 

arr = [100, 50, 70, 60, 87, 105, 78, 110, 60] 일 때

 

찾고자 하는 lis 배열은 

lis = [100]  이다. 

 

그 다음 arr의 1번 인덱스 부터 lis 배열에 들어갈 수 있는지 없는지 판정하는 것이다.

 

100 <= 50은 false 이므로 이진탐색으로 lis에서 50이 들어갈 인덱스를 찾는다.

 

lis = [100] 에서 lis = [50]으로 바뀐다. 

 

다음 arr의 2번 인덱스로부터 lis 배열에 들어갈 수 있는지 본다.

 

50 <= 70은 true 이므로 lis에 append 한다.

lis = [50, 70]이 된다.

 

다음 arr의 3번 인덱스로부터 lis 배열에 들어갈 수 있는지 본다.

 

70 <= 60 은 false 이므로 이진탐색으로 lis에서 60이 들어갈 인덱스를 찾는다.

lis = [50, 70] 에서 lis = [50, 60] 이 된다. 

 

즉 로직을 정리하면 다음과 같다.

로직 정리

1. 초기화
   배열의 첫 번째 값을 lis 배열의 유일한 원소로 저장하는 단계이다.
2. 순회 
   나머지 모든 원소를 순서대로 확인하며 lis 배열을 갱신하는 단계이다.
   • 현재 값이 lis 배열의 마지막 원소보다 큰 경우 라면
     부분 수열을 한 칸 늘릴 수 있으므로 lis 배열의 끝에 값을 추가한다.
   • 그렇지 않은 경우:
     lis 배열 내에서 현재 값이 위치해야 할 자리를 빠르게 찾기 위해 이진 탐색을 수행한다.
     이진 탐색으로 찾은 위치의 값을 현재 값으로 대체하여, 같은 길이의 부분 수열 중 끝값을 항상 최솟값으로 유지한다.
3. 결과 판단
   모든 원소를 처리한 뒤 lis 배열의 길이를 최장 증가 부분 수열의 길이로 판단한다.

코드

for num in range(int(input())):

    n,k = map(int, input().split())

    arr = list(map(int, input().split()))

    l = [arr[0]]

    for i in range(1,n):

        if l[-1] < arr[i]:

            l.append(arr[i])

        else:

            start,end = 0, len(l)-1

            while start <= end:

                mid = (start+end)//2

                if l[mid] >= arr[i]:

                    end = mid - 1

                else:

                    start = mid+ 1

            l[start] = arr[i]

    print("Case #"+str(num+1))

    if len(l) >= k:

        print(1)

    else:

        print(0)