https://www.acmicpc.net/problem/2352
2352번: 반도체 설계
첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.
www.acmicpc.net
1번 포트부터 n번 포트까지 연결이 꼬이지 않게 최대로 연결해야 하는 문제로 최장 증가수열문제이다.
12015번 가장 긴 증가하는 부분 수열 2 문제(문제 링크)와 똑같은 코드로 nlogn만에 풀 수 있다.
|
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;
//벡터의 가장 마지막 값보다 크다면(증가하는 순서) 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;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 17837. 새로운 게임 2 (0) | 2020.02.03 |
|---|---|
| [BOJ] 1600. 말이 되고픈 원숭이 (0) | 2020.02.01 |
| [BOJ] 12783. 가장 긴 증가하는 부분 수열 3 (0) | 2020.01.29 |
| [BOJ] 12015. 가장 긴 증가하는 부분 수열 2 (0) | 2020.01.29 |
| [BOJ] 1965. 상자넣기 (0) | 2020.01.29 |