백준 12014 (주식) - java

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

 

문제

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

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

의심을 더 줄이기 위해서, 주식을 살 때마다 맨 처음을 제외하고는 바로 직전에 주식을 샀을 때보다 가격이 올라갔을 때만 사기로 했다. 예를 들어, 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, 주가가 주어졌을때 주어진 조건을 만족하게 주식을 구입할 수 있는지 여부를 알려주는 프로그램을 작성하시오.

 

유형 : DP + 이진탐색

 

접근 방식

• 주식을 구매하는 경우는 바로 직전 구매 가격 보다 가격이 증가한 경우다. 즉 오름차순 형태로 구매해야 한다.
• 결국 주어진 N개의 주식 가격에 대해 LIS(가장 긴 길이의 증가 수열)을 구하고 해당 길이가 K 이상인지 판단하면 된다.
• LIS를 구하는 방법에는 DP, 이진 탐색이 있는데 테스트 케이스가 100개이므로 이진 탐색을 사용한다.

 

코드

import java.util.*;
import java.io.*;

public class BOJ_12014_주식 {

    static int t,n,m;
    static int[] arr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        t = Integer.parseInt(st.nextToken());

        StringBuilder sb = new StringBuilder();

        for(int tt = 1 ; tt <= t ; tt++) {
            st = new StringTokenizer(br.readLine()," ");
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

            arr = new int[n+1];

            int[] result = new int[n+1];
            int j = 1;

            st = new StringTokenizer(br.readLine()," ");
            for(int i = 1 ; i <= n ; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            result[j] = arr[1];

            for(int i = 1 ; i <= n ; i++) {
                if(result[j] < arr[i]) {
                    result[j+1] = arr[i];
                    j += 1;
                }else {
                    int idx = find(result,j,arr[i]);
                    result[idx] = arr[i];
                }
            }

            sb.append("Case #").append(tt).append("\n");
            int rr = j >= m ? 1 : 0;
            sb.append(rr).append("\n");
        }


        System.out.print(sb);
        br.close();
    }

    static void print(int[] result) {
        for(int i = 1  ; i <= n ; i++) {
            System.out.print(result[i]+", ");
        }
        System.out.println();
    }

    static int find(int[] arr, int j, int target) {
        int l = 1;
        int r = j;

        while(l <= r) {
            int mid = (l + r) / 2;

            if(arr[mid] >= target) {
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }

        return l;
    }
}