[백준 12014] 주식

문제

www.acmicpc.net/problem/12014

 

알고리즘

LIS, 이분 탐색

 

풀이

$N$일 동안의 주가가 주어졌을 때, $K$일 동안 첫날을 제외하고 직전 날 산 주가보다 비싸게 구매할 수 있는지를 묻고 있습니다.

 

유명한 Longest Increasing Subsequence 문제입니다. 다이나믹 프로그래밍으로 $O(N^2)$에 해결 가능합니다. 하지만 주어지는 테스트케이스가 100개에 $N$제한이 1만이므로 해당 알고리즘을 사용하면 시간 초과가 발생합니다.

 

처음에 정렬된 배열을 하나 갖고 시작합니다. 처음이므로 정렬된 빈 배열을 갖고 있습니다. $N$개의 값을 순차적으로 보며 해당 값을 정렬된 배열 어디에 위치한지 찾습니다. 정렬된 배열에서 위치를 찾는 것이므로 이분 탐색으로 찾을 수 있습니다. 위치를 찾았다면 해당 위치를 업데이트 하고 만약 배열의 길이와 해당 인덱스가 같다면 $len$을 증가시켜줍니다. 이는 정렬된 배열에서 맨 뒤에 값을 넣는 것과 동일합니다. 만들어진 배열의 길이는 $O(NlogN)$에 찾을 수 있는 LIS의 길이입니다. 정렬된 배열 안에는 실제 LIS값과는 다른 값이 들어있습니다. 

 

이분탐색으로 정렬된 배열을 업데이트 해주는 행동은 여러 subsequence들을 관리하는 것과 비슷합니다. 

배열 [1,5,10,2,4,7]이 주어졌을 때 정렬된 배열의 변화는 다음과 같습니다.

 

[1]

[1,5] 

[1,5,10]

[1,2,10] 

[1,2,4]

[1,2,4,7]

 

정렬된 배열의 상태가 [1,2,10] 일때 우리가 갖고 관리하는 subsequence들 중 정답 후보가 될 수 있는 것은 [1,5,10] 와 [1,2] 입니다. [1,2,10]으로 나타내어도 우리가 원하는 LIS의 길이를 구하는 것에는 전혀 지장이 없습니다. 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int tc,n,k;
int arr[10000];
int main() {
    FAST;
    cin >> tc;
    REP(CASE,tc) {
        cin >> n >> k;
        memset(arr, 0, sizeof(arr));
        int len = 0;
        
        rep(i, n) {
            int val;
            cin >> val;
            int pos = lower_bound(arr, arr + len, val) - arr;
            arr[pos] = val;
            if (len == pos) ++len;
        }
        cout << "Case #" << CASE << '\n';
        cout << (len >= k) << '\n';
    }
    return 0;
}