[백준/BOJ] 백준 12014번 : 주식

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

12014번: 주식

 

가장 긴 증가하는 부분 수열(n log n)을 찾아서 그 길이가 k이상인지 확인하는 방법을 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int t;
int n, k;
vector<int> stock;
vector<int> check;
vector<int>::iterator it;

void init() {
	stock.clear();
	check.clear();
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> t;

	for (int tc = 0; tc < t; tc++) {
		init();
		cin >> n >> k;

		for (int i = 0; i < n; i++) {
			int input;
			cin >> input;
			stock.push_back(input);
		}

		//가장 긴 증가하는 부분 수열(n log n) 찾기

		for (int i = 0; i < n; i++) {
			it = lower_bound(check.begin(), check.end(), stock[i]);

			if (it == check.end()) {
				check.push_back(stock[i]);
			}
			else {
				(*it) = stock[i];
			}
		}

		cout << "Case #" << tc + 1 << "\n";

		//가장 긴 증가하는 부분 수열이 k 이상일때
		if (check.size() >= k) {
			cout << 1 << "\n";
		}
		else {
			cout << 0 << "\n";
		}

	}

	return 0;
}