컴퓨터 사이언스/1고리즘
백준 12015 : 가장 긴 증가하는 부분 수열 2
저세상 개발자
2021. 9. 7. 01:17
https://www.acmicpc.net/problem/12015
12015번: 가장 긴 증가하는 부분 수열 2
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
www.acmicpc.net
LIS 문제다. N의 크기가 100만으로 O(N^2) 풀이는 시간 초과가 발생하니 O(NlogN)으로 해결하면 된다.
아래 문제와 거의 유사한 문제다.
https://unfunhy.tistory.com/112
백준 2352 : 반도체 설계
https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호,.
unfunhy.tistory.com
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
void solution() {
int tmp, target;
vector<int> ans;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> tmp;
if (ans.empty() || ans.back() < tmp) ans.push_back(tmp);
else {
target = lower_bound(ans.begin(), ans.end(), tmp) - ans.begin();
ans[target] = tmp;
}
}
cout << ans.size();
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solution();
return 0;
}| 메모리: 8292 kb | 시간: 176 ms |