문제링크 : https://www.acmicpc.net/problem/1965
DP - LIS 유형에 속하는 문제입니다.
이번에 DP 문제풀이를 처음 진행하면서 처음 만난 유형의 문제 입니다.
LIS 이란 '증가하는 최장수열' 이라는 것인데, 어떤 수열을 증가하는 방향으로 가장 길게 늘여뜨리는 문제 입니다.
개념은 쉽습니다. 하지만 어떻게 구현할 것이냐, 그것이 문제였습니다.
여기서 검색을 한 결과, STL에 적절한 방법이 있었습니다. 바로, 정렬된 상태의 벡터에 사용 가능한 lower_bound() 였습니다.
검색결과 이 lower_bound() 는 내부적으로 이분탐색을 사용한다고 합니다. 따라서 정렬된 상태여야 하죠. 우리는 LIS에서 증가하는 수열이므로 어떤 원소가 들어간다면 증가하는 방향으로 정렬이 되어있습니다. 이 부분을 만족하지요.
따라서 우리는 어떤 벡터가 있을 때 끝원소가 이번에 넣을 원소보다 작은 경우 벡터의 맨 뒤에 그냥넣고, 반대의 경우는 이번에 넣을 원소가 벡터의 어느 위치에 있을지 lower_bound() 를 사용하여 손쉽게 찾을 수 있습니다.
소스코드 :
DP - LIS 유형에 속하는 문제입니다.
이번에 DP 문제풀이를 처음 진행하면서 처음 만난 유형의 문제 입니다.
LIS 이란 '증가하는 최장수열' 이라는 것인데, 어떤 수열을 증가하는 방향으로 가장 길게 늘여뜨리는 문제 입니다.
개념은 쉽습니다. 하지만 어떻게 구현할 것이냐, 그것이 문제였습니다.
여기서 검색을 한 결과, STL에 적절한 방법이 있었습니다. 바로, 정렬된 상태의 벡터에 사용 가능한 lower_bound() 였습니다.
검색결과 이 lower_bound() 는 내부적으로 이분탐색을 사용한다고 합니다. 따라서 정렬된 상태여야 하죠. 우리는 LIS에서 증가하는 수열이므로 어떤 원소가 들어간다면 증가하는 방향으로 정렬이 되어있습니다. 이 부분을 만족하지요.
따라서 우리는 어떤 벡터가 있을 때 끝원소가 이번에 넣을 원소보다 작은 경우 벡터의 맨 뒤에 그냥넣고, 반대의 경우는 이번에 넣을 원소가 벡터의 어느 위치에 있을지 lower_bound() 를 사용하여 손쉽게 찾을 수 있습니다.
소스코드 :
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
39
40
41
42
43
44
|
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <string>
using namespace std;
int n;
vector<int> box(1001);
//vector<int> cache
vector<int> cache;
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
cin >> n;
cache.push_back(-1);
int ans = 0;
for (int i = 1; i <= n; i++) {
cin >> box[i];
if (cache.back() < box[i]) {
cache.push_back(box[i]);
ans++;
}
else {
auto it = lower_bound(cache.begin(), cache.end(), box[i]);
*it = box[i];
}
}
cout << ans;
}
| cs |
댓글
댓글 쓰기