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 문제이지만 11053번 가장 긴증가하는 부분 수열문제처럼 dp로 풀 수 없다.
dp로 풀면 시간 복잡도가 n제곱이 나오는데 이 문제는 n의 최댓값이 1,000,000이므로 n제곱으로 풀면 시간초과가 난다.
이분 탐색을 이용하여 nlogn만에 풀 수 있다.
0. 우선 입력으로 들어오는 최솟값보다 작은 값을 벡터에 넣어놓고 시작한다.
1. 값을 입력 받는다.
- 벡터의 맨 마지막 값보다 크다면(증가하는 순서라면) 입력받은 값을 벡터에 넣는다.
- 그렇지 않다면 이분탐색으로 벡터에 입력받은 값 이상의 값이 처음으로 나타나는 위치에 입력받은 값을 넣어준다.
(lower_bound를 이용하여 쉽게 구할 수 있다. )
2. 입력이 끝나면 벡터의 사이즈 -1한 값이 가장 긴 증가하는 부분 수열의 길이가 된다.
(처음에 넣어 놓은 값을 제외하기 위해 1을 뺀다)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector<int> vt;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
vt.push_back(0);
int num;
for (int i = 0; i < n; i++) {
cin >> num;
if (num > vt.back()) {
//벡터의 가장 마지막 값보다 크다면(증가하는 순서) push
vt.push_back(num);
}
else {
//num이상의 값이 처음으로 나타나는 위치에 num을 넣는다.
int index = lower_bound(vt.begin(), vt.end(), num) - vt.begin();
vt[index] = num;
}
}
//처음에 넣어놓은 0을 제외한 벡터의 사이즈가 최장 증가 수열의 길이
cout << vt.size() - 1 << '\n';
return 0;
}
hColored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 2532. 반도체 설계 (0) | 2020.01.29 |
|---|---|
| [BOJ] 12783. 가장 긴 증가하는 부분 수열 3 (0) | 2020.01.29 |
| [BOJ] 1965. 상자넣기 (0) | 2020.01.29 |
| [BOJ] 11053. 가장 긴 증가하는 부분 수열 (0) | 2020.01.29 |
| [BOJ] 2167. 2차원 배열의 합 (0) | 2020.01.24 |