[백준/BOJ] 11505번: 구간 곱 구하기 ( 세그먼트 트리 사용법 ) - C++ 문제 풀이

문제 설명

 

문제 풀이: https://www.acmicpc.net/problem/11505

 

풀이

이 문제는 주어진 숫자 배열의 값들을 변경한 후에, 변경된 값이 반영된 배열의 부분곱을 구하는 문제입니다.

 

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

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

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

 

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

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

 

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

using mtype = long;
#define MOD (1'000'000007)

vector<mtype> tree;

void setupTree( int idx){

    while( idx > 1){
        tree[idx/2] *= tree[idx];
        tree[idx/2] %= MOD;	// MOD 연산
        idx--;
    }
}

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

int N, M, K;

// N: 입력된 숫자의 개수
// M: 숫자를 변경할 연산의 수
// K: 부분곱을 구하는 연산의 수
cin >> N >> M >> K;

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);
fill( tree.begin(), tree.end(), 1); // 1로 초기화

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

setupTree(szTree-1);	// 부분곱을 구하기 위한 세그먼트 트리 구성

이번엔, 곱 연산의 값을 구해야 하므로, 세그먼트 트리를 초기화할 때, 0이 아니라 1을 사용해야 합니다.

그리고, 이 문제는 부분곱을 구하는 것이므로, setupTree 함수는 2개의 자식 노드로부터 곱한 값을 구해 부모 노드에 저장합니다.

 

이때, 곱한 값이 변수가 담을 수 있는 범위를 넘을 수 있기 때문에 MOD 연산을 해야 합니다.

여기서 사용한 MOD 연산 공식은 다음과 같습니다.

 

A, B, C가 정수일 때,

A * B mod C =  ( A mod C ) * ( B mod C ) mod C

 

이제, 명령 코드가 1인 경우, 주어진 인덱스의 값을 변경하는 연산을 하고, 코드가 2인 경우 주어진 인덱스 구간의 부분곱을 구합니다.

이를 코드로 작성하면 다음과 같습니다.

// 값을 변경하는 연산
void changeValue( int idx, mtype val){

    tree[idx] = val;

    while( idx > 1){
        idx /= 2;	// 부모의 노드로 이동
        tree[idx] = tree[idx*2] * tree[idx*2+1] % MOD;	// 자식 노드들의 곱한 값을 저장
    }
}

// 부분곱을 구하는 연산
mtype getParitalMultiply( int s, int e){
    mtype patialMul = 1;

    while( s <= e){
        if ( s % 2 == 1){
            patialMul *= tree[s];
            patialMul %= MOD;	
            s++;
        }

        if ( e % 2 == 0){
            patialMul *= tree[e];
            patialMul %= MOD;
            e--;
        }

        s /= 2;
        e /= 2;
    }

    return patialMul;
}

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

mtype a, b, c;
for(int i = 0; i < M + K; i++){
    cin >> a >> b >> c;

    if ( a == 1){
        changeValue( baseIndex + b, c );
    }
    else{
        mtype mul = getParitalMultiply( baseIndex + b, baseIndex + c);
        cout << mul << endl;
    }
}

위의 changeValue 함수는 부분합을 구할 때와 다르게, 부모 노드로 이동 후, 그 노드의 값을, 두 자식 노드들의 곱한 값으로 변경해야 됩니다.

 

 

소스 코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

using mtype = long;
#define MOD (1'000'000007)

vector<mtype> tree;

void setupTree( int idx){

    while( idx > 1){
        tree[idx/2] *= tree[idx];
        tree[idx/2] %= MOD;
        idx--;
    }
}

// 값을 변경하는 연산
void changeValue( int idx, mtype val){

    tree[idx] = val;

    while( idx > 1){
        idx /= 2;
        tree[idx] = tree[idx*2] * tree[idx*2+1] % MOD;
    }
}

// 부분곱을 구하는 연산
mtype getParitalMultiply( int s, int e){
    mtype patialMul = 1;

    while( s <= e){
        if ( s % 2 == 1){
            patialMul *= tree[s];
            patialMul %= MOD;
            s++;
        }

        if ( e % 2 == 0){
            patialMul *= tree[e];
            patialMul %= MOD;
            e--;
        }

        s /= 2;
        e /= 2;
    }

    return patialMul;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, K;
    cin >> N >> M >> K;

    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);
    fill( tree.begin(), tree.end(), 1); // 1로 초기화

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

    setupTree(szTree-1);

    mtype a, b, c;
    for(int i = 0; i < M + K; i++){
        cin >> a >> b >> c;

        if ( a == 1){
            changeValue( baseIndex + b, c );
        }
        else{
            mtype mul = getParitalMultiply( baseIndex + b, baseIndex + c);
            cout << mul << endl;
        }
    }
   
    return 0;
}