본문 바로가기

알고리즘 관련/BOJ

BOJ)11003 최소값 찾기

문제: icpc.me/11003


구간 n에서 ai-l+1 ~ai의 최솟값을 매번 찍어내는 문제이다.


RMQ 문제로 생각하여 세그트리나 multiset을 이용한 풀이를 예전에 제출했지만 n이 너무나도 커서 tle를 맞은 후 잊고 있던 문제였지만


오늘 다른 문제에서 다이나믹프로그래밍을 공부하다가 필요에 의해 다시 풀게 된 문제이다.


이 문제는 deque를 이용하여 해결할 수 있다.


연속 된 시퀀스에서 deque에는 pair형으로 해당 값과 해당 인덱스를 가지고 있을것이다.


우리는 답을 출력할 때 deque에 삽입 되어있는 구간에서 최솟값을 출력해야 하기때문에 앞이나 뒤에 최솟값을 가지고 있어야한다.


일단 deque의 front에 최솟값을 가지고 있다고 해보자.


그러면서 만약 deque의 front의 값의 인덱스가 현재 봐야할 구간을 벗어났다면 pop front를 해주면 된다.


그리고 deque의 뒤에서는 삽입을 해줄건데 현재 삽입하려는 값보다 deque의 back값이 크다면 pop back을 해주어야한다.


그 이유는 어짜피 구간의 최솟값을 뽑아내야하는데 현재 삽입하려는 값은 이미 있는 값보다 오래 존재하기 때문에 back의 값이 최솟값이 아니라면 필요없는 값이되기 때문이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
#include <algorithm>
#include <deque>
using namespace std;
int l, n, x;
deque<pair<intint>> dq;
int main() {
    scanf("%d%d"&n, &l);
    for (int i = 1; i <= n; i++) {
        while (dq.size() && dq.front().second <= i - l)dq.pop_front();
        scanf("%d"&x);
        while (dq.size() && dq.back().first >= x)
            dq.pop_back();
        dq.push_back({ x,i });
        printf("%d ", dq.front().first);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)5842 Partitioning the Farm  (0) 2017.09.07
BOJ)2337 트리 자르기  (1) 2017.09.05
BOJ)1460 진욱이의 농장  (0) 2017.09.05
BOJ)13548 수열과 쿼리 6  (0) 2017.09.03
BOJ)2419 사수아탕  (0) 2017.08.27