[Boj_12014] 주식, LIS

📎 문제 링크

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

 

▸ 문제

어느 날 당신은 출근길에, 지하철역 쓰레기통에서 놀라운 문서를 얻게 되었다. 이 문서는 미래의 어떤 회사의 주식 가격의 변동이 담겨 있었다. 설마 하는 마음으로 이 회사의 주식 가격의 변동을 본 결과, 문서에 담긴 내용이 사실이라는 것을 알게 되었다. 아마도 미래에서 타임머신을 타고 온 후손이 선조를 돕기 위해서 보낸 것이 아닐까 하는 마음이 들었다.

앞으로 N 일간 주식 가격이 N 개의 숫자로 주어져 있다. 당신은 지금까지 주식이라는 것을 거래해본 적이 없기 대문에, 증권회사에 가서 거래를 시작하기로 했다. 미래를 알면서 주식을 거래한다면 다른 사람들이 의심할지도 모른다는 생각이 들어서, 총 K 번 주식을 사기로 했다. 하루에는 주식을 한 번만 살수 있기 때문에, 주식을 사는 날은 총 K 일이다.

의심을 더 줄이기 위해서, 주식을 살 때마다 맨 처음을 제외하고는 바로 직전에 주식을 샀을 때보다 가격이 올라갔을 때만 사기로 했다. 예를 들어, 10일간 주가의 변동이 다음 표와 같다고 하자.

 

1	2	3	4	5	6	7	8	9	10
100	50	70	90	75	87	105	78	110	60

K=3이라면, 2일, 3일, 4일에 주식을 사면 그날의 주가는 50, 70, 90이기 대문에 주어진 조건을 만족한다. 만약 K=6이라면, 2일, 3일, 5일, 6일, 7일, 9일에 주식을 사면 주가가 50, 70, 75, 87, 105, 110이기 때문에 주어진 조건을 만족한다. K=10이라면 조건을 만족할 수 없다.

N과 K, 주가가 주어졌을때 주어진 조건을 만족하게 주식을 구입할 수 있는지 여부를 알려주는 프로그램을 작성하시오.

 

▸ 입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 두 정수 N과 K이 주어진다. N은 앞으로 주가를 알 수 있는 날 수이며, (1 ≤ N ≤ 10,000) K는 거래의 회수이다. (1 ≤ K ≤ 10,000) 다음 줄에는 앞으로 N 날의 주가가 사이에 공백을 두고 주어진다. 주가는 1부터 10,000 사이의 정수이다.

 

▸ 출력

각 테스트 케이스에 대해서 출력은 한 줄로 구성된다. T 번째 테스트 케이스에 대해서는 첫째 줄에는 "Case #T"를 출력한다. 두 번째 줄에는 주어진 조건을 만족하게 주식을 살 수 있으면 1, 아니면 0을 출력한다.

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 2
• 🔔  문제 유형 : 이분 탐색, 가장 긴 증가하는 부분 수열: o(n log n)
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

이 문제는 N일 간의 주식 가격이 주어졌을 때, K번 주식을 구매할 수 있는지 판단하는 문제이다. 단, 첫날을 제외하고는 이전에 구매한 날보다 가격이 오른 날에만 추가로 구매할 수 있다.

이를 해결하기 위해 가장 긴 증가하는 부분 수열(LIS)의 길이를 구한 뒤, 그 값이 k 이상인지 비교하면 된다. 이때, LIS의 길이는 이분 탐색을 활용하면 O(N log N)의 시간 복잡도로 구할 수 있다.

 

가장 긴 증가하는 부분 수열(LIS)란?

LIS(Longest Increasing Subsequence)란, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 의미한다. 이때, 부분 수열은 반드시 연속적일 필요 없으며, 유일하지 않을 수 있다.

arr

2

1

3

5

4

위와 같은 수열이 있다고 가정하자.

memo

2

먼저, LIS를 저장할 memo 배열을 만들어서, arr[0]의 값을 memo 배열의 첫 번째 값으로 넣는다.

memo

1

arr[1] = 1일때, 현재 memo의 마지막 값인 2보다 1이 작다.

이 경우, 이분 탐색을 사용해 들어갈 위치인 0번 인덱스를 찾고, 해당 위치의 값을 교체한다.

memo

1

3

arr[2] = 3 일때, 현재 memo 배열의 마지막 값인  1보다 3이 크다.

이 경우, 바로 맨 뒤에 값을 추가한다.

memo

1

3

5

arr[3] = 5일때, 현재  memo 배열의 마지막 값인 3보다 5가 크다.

이 경우, 바로 맨 뒤에 값을 추가한다.

memo

1

3

4

arr[4] = 4일때, 현재  memo 배열의 마지막 값인 5보다 4가 작다.

이 경우, 이분 탐색을 사용해 들어갈 위치인 2번 인덱스를 찾고, 해당 위치의 값을 교체한다.

 

최종적으로 memo = {1, 3, 4}이므로, LIS의 길이는 3이다.

 

즉, LIS를 유지하면서 새로운 원소가 들어갈 위치를 이분 탐색으로 찾아 삽입하거나 교체하는 방식으로 LIS를 구현한다.

 

위 풀이를 코드로 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 42096KB
시간 : 292ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n, k;
    static int[] stock;
    static int[] memo; // LIS를 저장할 배열
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int tIdx = 1;
        while (t --> 0) {
            sb.append("Case #").append(tIdx++).append("\n");
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken()); // 앞으로 주가를 알 수 있는 날 수
            k = Integer.parseInt(st.nextToken()); // 거래의 회수

            stock = new int[n];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                stock[i] = Integer.parseInt(st.nextToken());
            }
            memo = new int[n+1];
            int len = 0; // LIS 길이
            int idx; // 인덱스
            for (int i = 0; i < n; i++) {
                // 주식 가격이 현재 LIS의 마지막 값보다 크면, LIS 길이를 증가시키며 가격을 추가
                if (stock[i] > memo[len]) {
                    len += 1;
                    memo[len] = stock[i];
                } else {
                    // 그렇지 않으면, 이분 탐색을 통해 들어갈 위치를 찾아 해당 위치의 값을 교채
                    idx = binarySearch(0, len, stock[i]);
                    memo[idx] = stock[i];
                }
            }

            // LIS의 길이가 k 이상이면 1을 출력, 아니면 0을 출력
            if (len >= k) sb.append(1).append("\n");
            else sb.append(0).append("\n");
        }

        System.out.println(sb.toString());
    }

    // memo 배열에서 target이 들어갈 위치를 찾음
    private static int binarySearch(int start, int end, int target) {
        int mid;
        while (start < end) {
            mid = start+(end-start)/2;
            if (memo[mid] < target) {
                start = mid+1;
            } else end = mid;
        }
        
        return end;
    }
}

 

최근에 이분 탐색으로 다시 풀었던 가장 긴 증가하는 부분 수열 문제와 같은 문제였다. 

처음에는 이분 탐색을 활용해서 LIS를 구하는 풀이가 잘 이해 안 갔는데, 이 문제를 해결하고 풀이를 정리하는 과정에서 확실히 이해할 수 있어 좋았다. 해결 완료 ! 😎