BOJ 12014 주식(Java)

문제 탐색하기

• N 일간 주식 가격이 N 개의 숫자로 주어지며, 하루에 한 개씩 구매가 가능하다.
• 주식을 사는 날은 총 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을 출력한다.

코드 설계하기

구현 방법

1. LIS(Longest Increasing Subsequence) 알고리즘 사용
   • 주어진 주가 배열에서 가장 긴 증가하는 부분 수열의 길이를 구한다.
   • 이는 주식을 사는 날의 주가가 직전보다 높아야 하는 조건과 동일하다.
2. DP 배열 초기화
   • DP[i]는 i번째 날까지의 가장 긴 증가하는 부분 수열의 길이를 저장한다.
   • 초기값은 모든 위치에서 1로 설정한다.
3. LIS 계산
   • 각 위치 i에 대해, 0부터 i-1까지의 모든 위치 j를 확인한다.
   • 만약 arr[i] > arr[j]이면, DP[i]를 DP[j] + 1로 업데이트한다.
   • 이는 j번째 날에 주식을 사고 i번째 날에도 주식을 사는 경우를 의미한다.
4. 결정
   • DP 배열을 정렬하여 가장 긴 증가하는 부분 수열의 길이를 찾는다.
   • 이 길이가 K 이상이면 1을, 그렇지 않으면 0을 출력한다.

시간 복잡도

• 시간 복잡도: O(N²)
  • N은 주가를 알 수 있는 날 수이다.
  • LIS 알고리즘에서 이중 반복문을 사용하므로 O(N²)의 시간이 소요된다.
  • DP 배열 정렬은 O(N log N)이지만, N²에 비해 무시할 수 있다.
  • 최악의 경우 연산 횟수: N(N-1)/2 ≈ 50,000,000 (N=10,000일 때) 이므로 시간 내에 연산이 가능하다.
• 공간 복잡도: O(N)
  • 주가 배열과 DP 배열 각각 O(N)의 공간을 사용한다.

정답 코드 (Java)

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

public class b12014 {
    private static int N, K, ans = 0;
    private static int[] arr;
    private static int[] DP;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            arr = new int[N];
            DP = new int[N];
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
                DP[j] = 1;
            }

            LIS();

            // 가장 긴 증가하는 부분 수열의 길이가 K 이상이면 가능하고, 그 이하면 불가능이다.
            ans = DP[N - 1] >= K ? 1 : 0;

            bw.write("Case #" + (i + 1) + "\n" + ans + "\n");
        }

        bw.flush();
        bw.close();
        br.close();

    }

    // 가장 긴 증가하는 부분 수열의 길이를 구한다.
    private static void LIS() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    if (DP[i] < DP[j] + 1) {
                        DP[i] = DP[j] + 1;
                    }
                }
            }
        }

        Arrays.sort(DP);
    }
}