[BOJ 11003] 최솟값 찾기 - 모노톤 큐 없이 O(n)

https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

 

최솟값 찾기는 모노톤 큐를 사용해 푸는 풀이가 보편적인데 모노톤 큐를 사용하지 않는 \(O(n)\) 풀이를 소개하겠습니다.

 

1. 배열을 k개씩 묶음으로 쪼개 각각 묶음에서 prefix min, suffix min을 구한다.

2. min(prefix_min[i], suffix_min[i - k + 1])을 출력한다.

 

i mod k = 0인 i는 i - k + 1 <= t <= i인 t중에 반드시 하나가 존재한다. (i - k + 1 >= 0)

 

ex)

ㅇ ㅇ ㅇ ㅇ ㅁ ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ (k = 11)

ㅁ이 j mod k = 0인 j점이라고 할 때 ㅁ이 시작점도 끝점도 아닌 경우다.

suffix[i - k + 1]은 시작점부터 ㅁ이전 점까지의 최솟값을 저장하고 있으며 prefix_min[i]는 ㅁ부터 끝점까지의 최솟값을 저장하고 있으니

둘 중 작은 값을 취하면 된다.

 

위처럼 모든 경우에서 min(prefix_min[i], suffix_min[i - k + 1])이 답이 된다. i - k + 1 < 0인 경우는 prefix_min[i]를 출력하면 된다.

 

코드

 

#include "bits/stdc++.h"
#define pb push_back
#define endl '\n'

using namespace std;
using ll = long long;
const int di[4] = {0, -1, 0, 1}, dj[4] = {-1, 0, 1, 0};

int n, k;
int a[5050505];
int pre[5050505];
int suf[5050505];

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
template<typename T>
struct FASTIO {
    char *p,O[5000000],*d;
    void set() {
        struct stat st;fstat(0,&st);d=O;
        p=(char*)mmap(0,st.st_size,1,1,0,0);
    }
    ~FASTIO() {
        write(1,O,d-O);
    } 
    inline T get() {
        T x=0;bool e;p+=e=*p=='-';
        for(char c=*p++;c&16;x=10*x+(c&15),c=*p++);
        return e?-x:x;
    }
    inline void put(T x) {
        if(d-O>4500000)write(1,O,d-O),d=O;
        if(x<0) *d++='-', x=-x;
        char t[16],*q=t;
        do *q++=x%10|48; while(x/=10);
        do *d++=*--q; while(q!=t);
        *d++=32;
    }
};

FASTIO<int> IO;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    // freopen("input.txt", "r", stdin);

    IO.set();
    n = IO.get(); k = IO.get();
    for(int i = 0; i < n; a[i++] = IO.get());
    suf[n - 1] = a[n - 1];
    for(int i = n - 2; i >= 0; i--) {
        if(i % k < k - 1) suf[i] = min(suf[i + 1], a[i]);
        else suf[i] = a[i];
    }
    int pre;
    for(int i = 0; i < n; i++) {
        if(i % k) pre = min(pre, a[i]);
        else pre = a[i];
        if(i + 1 < k) IO.put(pre);
        else IO.put(min(pre, suf[i - k + 1]));
    }
}

 

썸넬용사진