728x90
반응형
12014번: 주식
문제
https://www.acmicpc.net/problem/12014
풀이
주가가 올랐을 때만 주식을 사고, 그리고 구매는 하루에 1번만 가능하고 최대 K번만 살 수 있다. 따라서 가장 긴 증가하는 부분 수열의 길이가 K 이상이면 조건을 만족하며 주식을 구매할 수 있다.
N의 범위는 10^4이지만 테스트 케이스의 수가 10^2 이므로 시간복잡도가 O(N^2) 알고리즘으로 풀면 최대 시간복잡도가 10^10이 되므로 시간복잡도가 O(NlogN)인 알고리즘으로 풀어야 한다. O(NlogN)으로 푸는 법은 아래 링크에 설명되어 있다.
[12015번 가장 긴 증가하는 부분 수열 2 문제] | [12015번 가장 긴 증가하는 부분 수열 2 풀이]
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
for (int j = 1; j <= t; j++) {
int n, k, x;
cin >> n >> k >> x;
vector<int> v{x};
for (int i = 1; i < n; i++) {
cin >> x;
if (v.back() < x)
v.push_back(x);
else
*lower_bound(v.begin(), v.end(), x) = x;
}
cout << "Case #" << j;
if (k > v.size())
cout << "\n0\n";
else
cout << "\n1\n";
}
return 0;
}
728x90
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
[백준 / BOJ] C++ 1818 책정리 (0) | 2023.03.17 |
---|---|
[백준 / BOJ] C++ 3066 브리징 시그널 (0) | 2023.03.16 |
[백준 / BOJ] C++ 9370 미확인 도착지 (0) | 2023.03.14 |
[백준 / BOJ] C++ 27868 On My Way Dorm (0) | 2023.03.13 |
[백준 / BOJ] C++ 1365 꼬인 전깃줄 (0) | 2023.03.13 |