[백준 12014] 주식 (C#, C++) - soo:bak

문제 링크

12014번 - 주식

설명

주가 수열에서 K번 주식을 구매해야 하며, 매수할 때마다 직전 매수일보다 주가가 높아야 하는 조건이 있습니다. 이는 주가 수열의 가장 긴 증가하는 부분 수열(LIS) 길이가 K 이상인지 판정하는 문제입니다.

접근법

이분 탐색 기반 LIS 알고리즘을 활용하여 가장 긴 증가하는 부분 수열의 길이를 구합니다.

먼저 lis 배열을 준비합니다. lis[i]는 길이가 i+1인 증가 부분 수열 중 가장 작은 마지막 값을 저장합니다.

다음으로 각 값 x에 대해 이분 탐색으로 lis 배열에서 x 이상인 첫 위치를 찾습니다. 해당 위치에 x를 넣고, 만약 배열 끝에 추가되는 경우라면 LIS 길이를 1 증가시킵니다.

이후 최종 LIS 길이가 K 이상이면 1을, 아니면 0을 출력합니다.

시간 복잡도는 O(N log N)입니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var tc = int.Parse(Console.ReadLine()!);
      for (var t = 1; t <= tc; t++) {
        var nk = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        var n = nk[0];
        var k = nk[1];
        var arr = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);

        var lis = new int[n];
        var len = 0;
        for (var i = 0; i < n; i++) {
          var x = arr[i];
          var idx = Array.BinarySearch(lis, 0, len, x);
          if (idx < 0)
            idx = ~idx;
          lis[idx] = x;
          if (idx == len)
            len++;
        }

        Console.WriteLine($"Case #{t}");
        Console.WriteLine(len >= k ? 1 : 0);
      }
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int tc; cin >> tc;
  for (int t = 1; t <= tc; t++) {
    int n, k; cin >> n >> k;
    vi a(n);
    for (int i = 0; i < n; i++)
      cin >> a[i];

    vi lis(n);
    int len = 0;
    for (int x : a) {
      auto it = lower_bound(lis.begin(), lis.begin() + len, x);
      *it = x;
      if (it == lis.begin() + len)
        len++;
    }

    cout << "Case #" << t << "\n";
    cout << (len >= k ? 1 : 0) << "\n";
  }

  return 0;
}