[백준/BOJ] 10868번: 최솟값 ( 세그먼트 트리 사용법 ) - C++ 문제 풀이

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/10868

 

풀이

이 문제는 입력된 숫자 배열에서 주어진 구간의 최소 값을 구하는 문제입니다.

 

이번 문제는 세그먼트 트리( segment )를 사용하는 전형적인 문제입니다.

세그먼트 트리는 주어진 데이터에 대한 빈번한 변경에도, 원하는 연산 값을 구하는데, 일정한 수행 능력을 보여주는 자료구조입니다.

세그먼트 트리의 값은 수행하고자 하는 연산에 따라 달라지는데, 이 문제에선 원하는 연산이 부분 최소 값을 구하는 것입니다.

 

세그먼트 트리에 관한 내용은 여기에서 볼 수 있습니다.

[C++] 세그먼트 트리( segment tree )에 관한 설명과 사용법

 

먼저, 주어진 데이터로부터 세그먼트 트리를 구성합니다.

using mtype = int;

vector<mtype> tree;

void setupTree( int idx){	// 세그멘트 트리 구성

    while( idx > 1){
        tree[idx/2] = min( tree[idx-1], tree[idx]);
        idx-=2;
    }
}

//-------------------------------------------------------

int N, M;
N = readInt();	// 숫자의 개수
M = readInt();	// 최소 값을 구하는 연산의 개수

int TreeHeight = 1;
int val = N;
while(val > 0){
    val = val / 2;
    TreeHeight++;
}
int szTree = pow( 2, TreeHeight );
int baseIndex = szTree / 2 - 1;

tree.resize(szTree);

for(int i = 1; i <= N; i++){
    tree[baseIndex + i] = readInt();
}

setupTree(szTree-1);	// 세그멘트 트리 구성

이 문제는 최소 값을 구하는 것이므로, setupTree 함수는 2개의 자식 노드의 값을 비교해서 최소 값을 부모 노드에 저장합니다.

 

이제, 주어진 구간으로부터 부분 최소 값을 구해서 출력하면 문제 해결입니다.

using mtype = int;

// 부분 최소 값을 구하는 연산
mtype getPartialMinimum( int s, int e){
    mtype minVal = INT_MAX;	// 임의의 최대 값으로 초기화

    while( s <= e){
        if ( s % 2 == 1){
            minVal = min( minVal, tree[s]);
            s++;
        }

        if ( e % 2 == 0){
            minVal = min( minVal, tree[e]);
            e--;
        }

        s /= 2;
        e /= 2;
    }

    return minVal;
}

// -----------------------------------------------------------------

mtype a, b;
for(int i = 0; i < M; i++){
    a = readInt();
    b = readInt();

    mtype mimimum = getPartialMinimum( baseIndex + a, baseIndex + b);
    printf("%d\n", mimimum);
}

 

 

소스 코드

#include <iostream>
#include <vector>
#include <cmath>
#include <limits.h>
using namespace std;

// 입출력 소스 --------------------------------------------
#define WBUF_SIZE (1 << 20)

char rbuf[WBUF_SIZE];
int ridx, nidx;

inline char read() {
    if (ridx == nidx) {
        nidx = fread(rbuf, 1, 1 << 20, stdin);
        if (!nidx) return 0;
        ridx = 0;
    }
    return rbuf[ridx++];
}
inline int readInt() {
    int sum = 0;
    char now = read();
    bool flg = false;

    while (now <= 32) now = read();
    if (now == '-') flg = true, now = read();
    while (now >= 48) sum = sum * 10 + now - '0', now = read();

    return flg ? -sum : sum;
}
//----------------------------------------------------------

using mtype = int;

vector<mtype> tree;

void setupTree( int idx){

    while( idx > 1){
        tree[idx/2] = min( tree[idx-1], tree[idx]);
        idx-=2;
    }
}

// 부분 최소 값을 구하는 연산
mtype getPartialMinimum( int s, int e){
    mtype minVal = INT_MAX;

    while( s <= e){
        if ( s % 2 == 1){
            minVal = min( minVal, tree[s]);
            s++;
        }

        if ( e % 2 == 0){
            minVal = min( minVal, tree[e]);
            e--;
        }

        s /= 2;
        e /= 2;
    }

    return minVal;
}

int main(){

    int N, M;
    N = readInt();
    M = readInt();

    int TreeHeight = 1;
    int val = N;
    while(val > 0){
        val = val / 2;
        TreeHeight++;
    }
    int szTree = pow( 2, TreeHeight );
    int baseIndex = szTree / 2 - 1;

    tree.resize(szTree);

    for(int i = 1; i <= N; i++){
        tree[baseIndex + i] = readInt();
    }

    setupTree(szTree-1);

    mtype a, b;
    for(int i = 0; i < M; i++){
        a = readInt();
        b = readInt();

        mtype minimum = getPartialMinimum( baseIndex + a, baseIndex + b);
        printf("%d\n", minimum);
    }
   
    return 0;
}