https://www.acmicpc.net/problem/11003
정수 배열에 대해, 각 인덱스로 자신이 부분수열의 끝이고 길이가 L인 부분수열을 만들 수 있다.
각 부분수열의 최소값을 구해야 한다. (정수 배열의 길이 <= 오백만)
처음엔 세그먼트 트리 풀이만 생각이 났다. 근데 오백만이라 nlogn만 해도 오억이라 시간안에 풀 수 없었다.
복잡한 세그먼트 트리로만 헤매고 있었던 이유는,
각 부분수열의 최소값을 구할 때, 전 인덱스로 구한 최소값을 활용하는게 어려웠기 때문이다.
최소값이 부분수열의 맨 처음에 있었다면, 이번에 최소값을 구할 땐, 이전의 최소값은 구간에 포함이 안되고 새로 구해야 했다.
이러한 최악의 경우는 계속 일어날 수 있고(오름차순 정렬된 배열이라면), 좋은 풀이가 아니었다.
결국 이렇게 최악의 경우에서, 다음으로 작은 최소값을 알고 있으면 해결할 수 있다.
이 최소값도 다시 구간에서 벗어날 수 있으므로, 최소값들 후보를 죄다 갖고 있으면 된다!
이러한 자료구조를 고민하다가 덱을 쓰기로 했다.
덱의 맨 앞은 최소값을 가지고, 뒤로 갈수록 다음 최소값 후보들이 이어진다.
따라서 덱의 front에선 최소값들을 활용하고, 뒤로는 최소값 후보들을 집어넣으면 된다.
작업후에는 L-i ~ i 까지 최소값들 후보들이 덱에 들어가 있을 것이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include <stdio.h> #include <deque> #include <algorithm> using namespace std; int n, l, a; deque<pair<int, int>> dq; int main() { scanf("%d %d", &n, &l); for (int i = 0; i < n; ++i) { while (dq.size() && dq.front().second <= i - l) dq.pop_front(); scanf("%d", &a); while (dq.size() && dq.back().first >= a) dq.pop_back(); dq.push_back({ a,i }); printf("%d ", dq.front().first); } return 0; } | cs |
'알고리즘 > 미분류' 카테고리의 다른 글
| SCC 문제들! 백준) 2150, 4013, 4196 (0) | 2018.07.22 |
|---|---|
| 백준) 2512 예산 (0) | 2018.07.19 |
| 중위표기법을 후위표기법으로 바꿔서 계산하는 알고리즘 (0) | 2018.02.22 |
| 백준) 2257 화학식량 (0) | 2018.01.31 |
| 백준) 2841 외계인의 기타 연주 (0) | 2018.01.22 |