[백준OJ] 12837번 가계부 (Hard) - Java

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

12837번: 가계부 (Hard)

---

풀이

세그먼트 트리를 이용하여 문제를 해결했습니다.

 

먼저 세그먼트 트리는 완전 이진트리의 모양을 띄기 때문에 먼저 선언을 해주어야 하는데, 간편하게 4*N의 높이로 설정을 해주며 세그먼트 트리를 생성해주었습니다.

static class SegTree {
        long tree[];

        public SegTree(int n) {
            tree = new long[4 * n];
        }
}

 

문제의 1번 Operation은 p일에 x원의 변화를 추가시켜주는 명령어입니다.

이는 세그먼트트리의 update와 비슷합니다. 세그먼트 트리를 탐색하며 p를 포함하는 범위는 모두 업데이트 해주며 내려갑니다.

static class SegTree {
    long tree[];

    public SegTree(int n) {
        tree = new long[4 * n];
    }

    public void update(int node, int left, int right, int target, int value) {
        if (target < left || right < target) {
            return;
        }
        tree[node] += value;
        if (left != right) {
            int middle = (left + right) >> 1;
            update(node * 2, left, middle, target, value);
            update(node * 2 + 1, middle + 1, right, target, value);
        }
    }
}

 

2번 Operation은 p~q일까지의 변화량의 합을 구하는 명령어 입니다.

세그먼트 트리의 sum과 같기때문에 똑같이 구현해줍니다.

static class SegTree {
    long tree[];

    public SegTree(int n) {
        tree = new long[4 * n];
    }

    public void update(int node, int left, int right, int target, int value) {
        if (target < left || right < target) {
            return;
        }
        tree[node] += value;
        if (left != right) {
            int middle = (left + right) >> 1;
            update(node * 2, left, middle, target, value);
            update(node * 2 + 1, middle + 1, right, target, value);
        }
    }

    public long sum(int node, int left, int right, int start, int end) {
        if (end < left || right < start) {
            return 0;
        }
        if (start <= left && right <= end) {
            return tree[node];
        }

        int middle = (left + right) >> 1;
        return sum(node * 2, left, middle, start, end) + sum(node * 2 + 1, middle + 1, right, start, end);
    }
}

 

이 SegmentTree를 이용하여 문제를 해결해줍니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static class SegTree {
        long tree[];

        public SegTree(int n) {
            tree = new long[4 * n];
        }

        public void update(int node, int left, int right, int target, int value) {
            if (target < left || right < target) {
                return;
            }
            tree[node] += value;
            if (left != right) {
                int middle = (left + right) >> 1;
                update(node * 2, left, middle, target, value);
                update(node * 2 + 1, middle + 1, right, target, value);
            }
        }

        public long sum(int node, int left, int right, int start, int end) {
            if (end < left || right < start) {
                return 0;
            }
            if (start <= left && right <= end) {
                return tree[node];
            }

            int middle = (left + right) >> 1;
            return sum(node * 2, left, middle, start, end) + sum(node * 2 + 1, middle + 1, right, start, end);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.valueOf(st.nextToken());
        int q = Integer.valueOf(st.nextToken());

        SegTree segTree = new SegTree(n);

        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int op = Integer.valueOf(st.nextToken());
            int p = Integer.valueOf(st.nextToken());
            int x = Integer.valueOf(st.nextToken());

            if (op == 1) {
                segTree.update(1, 1, n, p, x);
            } else {
                System.out.println(segTree.sum(1, 1, n, p, x));
            }
        }
    }
}