어흥
[백준 12738] 가장 긴 증가하는 부분 수열 3 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/12738
1. 주의할 점
- 이분탐색을 사용하는 LIS에 대해 알고 있어야 한다.
- 가장 긴 증가하는 부분 수열 2와 풀이 방법은 같다. 다른점은 모든 변수를 Int가 아닌 Long Long으로 받아들인다.
풀이 방법: https://imnotabear.tistory.com/183
#include <iostream>
using namespace std;
long long arr[1000000], dp[1000000], idx = 0, num;
long long binary_search(long long val) {
long long l = 0, r = idx, mid, result = idx;
while (l <= r) {
mid = l + (r - l) / 2;
if (dp[mid] >= val) {
result = mid;
r = mid - 1;
}
else
l = mid + 1;
}
return result;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> num;
for (int i = 0; i < num; i++)
cin >> arr[i];
dp[0] = arr[0];
for (int i = 1; i < num; i++) {
if (dp[idx] < arr[i]) {
dp[++idx] = arr[i];
}
else {
long long v = binary_search(arr[i]);
dp[v] = arr[i];
}
}
cout << idx + 1;
system("pause");
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 17086] 아기 상어 2 (C++) (0) | 2020.05.22 |
---|---|
[백준 14003] 가장 긴 증가하는 부분 수열 5 (C++) (0) | 2020.05.17 |
[백준 12015] 가장 긴 증가하는 부분 수열 2 (C++) (0) | 2020.05.17 |
[백준 14002] 가장 긴 증가하는 부분 수열 4 (C++) (0) | 2020.05.17 |
[백준 16434] 드래곤 앤 던전 (C++) (0) | 2020.05.17 |
Comments