[C/C++] 백준 - 12014번 : 주식

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

12014번: 주식

 

 

N일 동안 주식을 K일 동안 살건데, K일 동안의 주식 가격은 모두 상승세이어야한다.

가장 긴 증가하는 부분 수열을 구했을 때 길이가 K를 만족하면 위 조건을 만족하고, K일 간의 가장 긴 증가하는 부분 수열을 구하지 못한다면 K일 동안 주식을 살 수 없다.

 

즉, 가장 긴 증가하는 부분 수열 알고리즘을 이용하여 길이만 만족하는지 확인하면 되는 문제

LIS알고리즘은 이분 탐색을 응용한 O(nlogn)을 이용하여야 한다.

 

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 

#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int solution(vector<int> &ps, int k) {
	vector<int> ret;
	for (auto& ptr : ps) {
		if (ret.empty()) ret.push_back(ptr);
		else {
			if (ret.back() < ptr) ret.push_back(ptr);
			else {
				int pos = lower_bound(ret.begin(), ret.end(), ptr) - ret.begin();
				ret[pos] = ptr;
			}
		}
		if (ret.size() == k) return 1;
	}
	return 0;
}

void input() {
	int N, K;
	int testCase; cin >> testCase;
	for (int T = 1; T <= testCase; T++) {
		cin >> N >> K;
		vector<int> price(N, 0);
		for (int i = 0; i < N; i++) cin >> price[i];
		cout << "Case #" << T << endl << solution(price, K) << endl;
	}
}

int main() {
	fastio;
	input();
	 
	return 0;
}