[C++ 백준 풀이] 11505번 : 구간 곱 구하기 / 2268번 : 수들의 합 7 (세그먼트 트리 응용)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 11505번 : '구간 곱 구하기' 문제와 2268번 : '수들의 합 7' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 두 문제 모두 Gold I에 해당하며, 문제를 풀이하기 위해 세그먼트 트리 응용에 대한 개념을 다룰 것입니다.

 

 

11505번 : 구간 곱 구하기

 

N개의 수가 주어졌을 때, 두 가지 종류의 쿼리를 처리하는 문제입니다.

쿼리 1에 대해서는 b번째 수를 c로 바꾸는 처리를 하면 되고, 쿼리 2에 대해서는 b번째부터 c번째 수까지의 곱을 구하여 출력하면 됩니다.

데이터의 수와 명령의 수가 많고, 구간 곱을 구하는 과정 자체에서 시간이 소요되기 때문에 구간 곱을 세그먼트 트리에 저장해서 풀이해야 합니다.

 

다만 세그먼트 트리에서 곱을 다룰 때 기존의 세그먼트 트리와 다른 부분들이 있으므로 그 부분들에 주의해서 코드를 작성해야 합니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <vector>
#define MODULER 1000000007
using namespace std;

vector<long long> Arr, Tree;

long long initTree(int Begin, int End, int Node) {
    if(Begin == End) return Tree[Node] = Arr[Begin];
    int Mid = (Begin+End)/2;
    long long leftKey = initTree(Begin, Mid, Node*2);
    long long rightKey = initTree(Mid+1, End, Node*2+1);
    return Tree[Node] = (leftKey * rightKey) % MODULER;
}

long long updateTree(int Begin, int End, int Node, int Index, int Value) {
    if(Index > End || Index < Begin) return Tree[Node];
    if(Begin == End) return Tree[Node] = Value;
    int Mid = (Begin+End)/2;
    long long leftKey = updateTree(Begin, Mid, Node*2, Index, Value);
    long long rightKey = updateTree(Mid+1, End, Node*2+1, Index, Value);
    return Tree[Node] = (leftKey * rightKey) % MODULER;
}

long long calcAns(int Begin, int End, int Node, int Left, int Right) {
    if(Left > End || Right < Begin) return 1;
    if(Left <= Begin && Right >= End) return Tree[Node];
    int Mid = (Begin+End)/2;
    long long leftKey = calcAns(Begin, Mid, Node*2, Left, Right);
    long long rightKey = calcAns(Mid+1, End, Node*2+1, Left, Right);
    return (leftKey * rightKey) % MODULER;
}

int main() {
    int N, M, K, a, b, c;
    scanf("%d %d %d", &N, &M, &K);
    Arr.resize(N);
    for(int i=0; i<N; i++) scanf("%lld", &Arr[i]);
    Tree.resize(N*4);
    initTree(0, N-1, 1);
    for(int i=0; i<M+K; i++) {
        scanf("%d", &a);
        if(a == 1) {
            scanf("%d %d", &b, &c);
            updateTree(0, N-1, 1, b-1, c);
        }
        else {
            scanf("%d %d", &b, &c);
            printf("%lld\n", calcAns(0, N-1, 1, b-1, c-1));
        }
    }
}

 

프로그램의 큰 틀 자체는 기존의 세그먼트 트리를 다루는 코드와 동일하지만, 일부 다른 점들이 있습니다.

먼저 initTree에서 Tree[Node] 값을 계산할 때 (leftKey * rightKey) % 1000000007으로 계산해주어야 합니다.

updateTree에서 값을 갱신할 때 leaf 노드는 바로 Value로 바꾸어줍니다. (노드 1개의 곱은 그 수 자체이기 때문)

그 외 return 값은 역시 (leftKey * rightKey) % 1000000007으로 동일합니다.

구간의 곱을 구하는 함수인 calcAns에서 범위를 벗어나는 경우 1을 리턴해주어야 합니다.

예를 들어 0을 리턴해버리면 구간의 곱이 0이 되어버리게 됩니다.

 

 

나머지 부분은 기존의 세그먼트 트리 기본 코드와 동일하므로 그대로 작성해주시면 됩니다.

풀이 코드를 제출해보면 220ms라는 짧지는 않은 시간에 문제가 해결되었음을 확인할 수 있습니다.

 

 

2268번 : 수들의 합 7

 

이 문제 역시 두 가지 쿼리를 처리하는 문제입니다.

쿼리 0에 대해서는 Sum 함수를 구현하여 i번째 수부터 j번째 수까지의 합을 출력해주면 됩니다.

쿼리 1에 대해서는 i번째 수를 k로 값을 변경해주는 처리를 수행해주면 됩니다.

문제 조건에서 주의해야 할 점 두 가지가 있는데, 하나는 초기 배열의 값이 모두 0이므로 배열 입력을 따로 받을 필요가 없다는 점, 그리고 0 i j가 입력될 때 i가 j보다 작다는 조건이 없다는 것입니다.

따라서 i가 j보다 큰 경우 두 수를 swap 처리해주는 예외를 다루어야 합니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <vector>
using namespace std;

vector<int> Arr;
vector<long long> Tree;

long long calcSum(int Begin, int End, int Node, int Left, int Right) {
    if(Left > End || Right < Begin) return 0;
    if(Left <= Begin && Right >= End) return Tree[Node];
    int Mid = (Begin+End)/2;
    long long LeftKey = calcSum(Begin, (Begin+End)/2, Node*2, Left, Right);
    long long RightKey = calcSum((Begin+End)/2+1, End, Node*2+1, Left, Right);
    return LeftKey + RightKey;
}

void updateTree(int Begin, int End, int Node, int Index, int Diff) {
    if(Index < Begin || Index > End) return;
    Tree[Node] += (long long)Diff;
    int Mid = (Begin+End)/2;
    if(Begin < End) {
        updateTree(Begin, Mid, Node*2, Index, Diff);
        updateTree(Mid+1, End, Node*2+1, Index, Diff);
    }
}

int main() {
    int N, M, a, b, c;
    scanf("%d %d", &N, &M);
    Arr.resize(N);
    Tree.resize(N*4);
    for(int i=0; i<M; i++) {
        scanf("%d %d %d", &a, &b, &c);
        if(!a) {
            if(b > c) { int temp = b; b = c; c = temp; }
            printf("%lld\n", calcSum(0, N-1, 1, b-1, c-1));
        }
        else {
            int Diff = c - Arr[b-1];
            Arr[b-1] = c;
            updateTree(0, N-1, 1, b-1, Diff);
        }
    }
}

 

일반적으로 자료 구조들은 기본적으로 값이 0으로 차 있으므로 값을 갱신해줄 필요는 없고, 단순히 resize로 벡터의 크기만 설정해주면 됩니다.

a가 0인 경우에 대해서는 우선 b와 c의 크기 비교로 조건에 따라 swap을 해주고, calcSum 함수를 통해 세그먼트 트리의 구간 합을 리턴하도록 구현하였습니다.

a가 1인 경우에 대해서는 update를 구현해야 하므로, diff 값을 구해서 root node에서부터 따라 내려가면서 diff 값들을 더해주는 수행을 하였습니다.

 

 

풀이 코드를 제출해보면 위와 같이 924ms라는 1초에 아슬아슬한 시간에 정답 처리를 받을 수 있습니다.

(물론 문제 제한 시간은 2초이긴 합니다.)