[C++ 백준 풀이] 5676번 : 음주 코딩 / 12837번 : 가계부 (Hard) (세그먼트 트리 응용)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 5676번 : '음주 코딩', 12837번 : '가계부 (Hard)' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

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

 

 

5676번 : 음주 코딩

 

문제에서 필요한 부분만 잘라서 편집해왔습니다.

수열을 입력 받고 두 가지 쿼리를 반복적으로 처리하는 문제입니다.

C로 시작하는 변경 명령은, 특정 인덱스의 값을 다른 값으로 변경하는 쿼리입니다.

P로 시작하는 곱셈 명령은, 특정 인덱스부터 특정 인덱스까지의 곱을 계산하여 양수일 경우 +, 음수일 경우 -, 0일 경우 0을 출력하는 쿼리입니다.

 

만약 쿼리의 출력문이 + 또는 - 두 가지 중 하나뿐이었다면 세그먼트 트리를 bool로 처리할 수 있겠지만, 0인 경우도 계산을 해야하기 때문에 그냥 구간 곱을 저장하는 트리를 구현할 것입니다.

다만 이 때 구간 곱을 계산하면 당연히 자료형의 범위를 벗어나기 때문에, 각 입력되는 값을 1, -1, 0으로 바꾸어서 트리에 대입할 것입니다.

그렇게 한다면 곱을 아무리 하더라도 부호나 0으로만 바뀌고, 오버플로우를 염려할 필요가 없게 되기 때문입니다.

 

 

코드 이미지가 길어서 옆으로 부분을 잘라왔습니다.

이미지가 잘 안 보이신다면 클릭해서 확대해서 보셔도 되고, 접은 글의 텍스트를 보시는 것을 권장합니다.

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

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

int updateTree(vector<int> &Tree, int Node, int Begin, int End, int Index, int Value) {
    if(Index < Begin || Index > End) return Tree[Node];
    if(Begin == End) return Tree[Node] = Value;
    int Mid = (Begin+End)/2;
    int leftVal = updateTree(Tree, Node*2, Begin, Mid, Index, Value);
    int rightVal = updateTree(Tree, Node*2+1, Mid+1, End, Index, Value);
    return Tree[Node] = leftVal * rightVal;
}

int calcMul(vector<int> &Tree, int Node, int Begin, int End, int Left, int Right) {
    if(Left > End || Right < Begin) return 1;
    if(Left <= Begin && Right >= End) return Tree[Node];
    int Mid = (Begin+End)/2;
    int leftVal = calcMul(Tree, Node*2, Begin, Mid, Left, Right);
    int rightVal = calcMul(Tree, Node*2+1, Mid+1, End, Left, Right);
    return leftVal*rightVal;
}

int main() {
    int N, K, Index, Value, Left, Right, Mul;
    char Q;
    while(scanf("%d %d", &N, &K) != EOF) {
        vector<int> Tree;
        vector<pair<char, pair<int, int>>> Query;
        Tree.resize(4*N+1);
        for(int i=1; i<=N; i++) {
            scanf("%d", &Value);
            if(Value > 0) Value = 1;
            else if(Value < 0) Value = -1;
            updateTree(Tree, 1, 1, N, i, Value);
        }
        for(int i=0; i<K; i++) {
            char a; int b, c;
            scanf(" %c %d %d", &a, &b, &c);
            Query.push_back({a, {b, c}});
        }
        for(int i=0; i<K; i++) {
            Q = Query[i].first;
            if(Q == 'C') {
                Index = Query[i].second.first;
                Value = Query[i].second.second;
                if(Value > 0) Value = 1;
                else if(Value < 0) Value = -1;
                updateTree(Tree, 1, 1, N, Index, Value);
            }
            else if(Q == 'P') {
                Left = Query[i].second.first;
                Right = Query[i].second.second;
                Mul = calcMul(Tree, 1, 1, N, Left, Right);
                if(Mul > 0) printf("+");
                else if(Mul < 0) printf("-");
                else printf("0");
            }
        }
        printf("\n");
    }
}

 

먼저 이 문제에는 입력의 종료를 알리는 입력이나 테스트케이스의 수가 정해져있지 않으므로, while문과 EOF를 활용해서 입력의 종료를 인식하도록 설계해야 합니다.

또한 입력되는 쿼리와 출력을 확실히 구분하기 위해 모든 쿼리를 벡터에 저장하는 과정을 거쳤는데, 이것은 굳이 없어도 정답 여부에는 영향을 주지 않습니다.

 

값이 초기에 입력되는 경우하고 값이 변경되는 쿼리에 대해, Value를 입력받으면 이것이 양수일 경우 1로, 음수일 경우 -1로 변경해서 함수에 대입해줄 수 있도록 합니다.

나머지 처리 부분은 일반적인 세그먼트 트리의 구현과 같습니다.

 

 

위의 풀이 코드를 제출해보면 짧지는 않은 시간에 모든 테스트케이스를 통과함을 확인할 수 있습니다.

이 문제에서 가장 주의할 점은 초기 값을 입력하는 부분과 쿼리 C를 처리하는 과정 모두에서 Value를 1과 -1로 변경해주어야 한다는 점입니다.

둘 중 하나를 놓친다면 당연히 overflow가 발생하게 되니, 이 부분을 주의해주면 좋습니다.

 

 

12837번 : 가계부 (Hard)

 

이 문제는 특정 날짜의 수입이나 지출을 입력받고, 특정 구간 동안의 순이익을 출력하는 문제입니다.

중간에 지출만 있었다면 당연히 순이익이 음수가 되므로 부호를 신경써야 합니다.

이 문제 역시 특정 구간의 합을 구하는 문제이므로 세그먼트 트리를 이용하여 구현하면 됩니다.

 

 

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

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

vector<long long> Tree;

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

long long calcSum(int Node, int Begin, int End, 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 leftSum = calcSum(Node*2, Begin, Mid, Left, Right);
    long long rightSum = calcSum(Node*2+1, Mid+1, End, Left, Right);
    return leftSum + rightSum;
}

int main() {
    int N, M, Q, Index, Diff, Left, Right;
    scanf("%d %d", &N, &M);
    Tree.resize(4*N+1);
    for(int i=0; i<M; i++) {
        scanf("%d", &Q);
        if(Q == 1) {
            scanf("%d %d", &Index, &Diff);
            updateTree(1, 1, N, Index, Diff);
        }
        else {
            scanf("%d %d", &Left, &Right);
            printf("%lld\n", calcSum(1, 1, N, Left, Right));
        }
    }
}

 

이 문제는 세그먼트 트리 문제를 많이 풀었다면 오히려 헷갈릴 수가 있는데, 입력을 처리하는 쿼리 즉 updateTree 함수를 호출해야 하는 부분에서 값을 수정하는 것이 아니라 그냥 추가 손익을 입력하는 것이기 때문에 변화량만 계속 계산해주면 됩니다.

보면 Arr 벡터를 활용하지 않고 바로 Diff로 값을 대입해주는 것을 확인할 수 있습니다.

그렇기 때문에 구현 자체는 다른 문제들에 비해 더 쉬웠으나 위의 포인트를 간과했다면 구현까지 다 해놓고 코드를 다시 지워야 되는 불상사가 발생할 수 있습니다.

나머지 구현에 대해서는 일반적인 세그먼트 트리와 똑같이 해주면 됩니다.

 

 

풀이를 제출해보면 100ms라는 시간에 모든 테스트케이스를 통과함을 확인할 수 있습니다.