[자바] 백준 16404 - 주식회사 승범이네 (java)

 문제 : boj16404

---

 

필요 알고리즘 개념

• lazy propagation을 적용한 세그먼트 트리 혹은 펜윅 트리
  • 세그먼트 트리 + lazy propagation 혹은 range update가 가능한 펜윅 트리를 알고 있어야 풀 수 있다.
• 오일러 경로 테크닉
  
  • 트리를 펴서 구간을 만드는 오일러 경로 테크닉이 필요하다. 어려운 개념도 아니고, 기존에 모르는 상태로도 얼마든지 생각해낼 수 있는 부분이라 반드시 알고있어야하는 부분은 아니다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  명령1에서 직원 i가 입은 이익/손해가 그 부사수들에게도 연쇄적으로 영향을 끼친다. 따라서 range update로 볼 수 있다. 그리고 '명령2에서는 직원 i의 현재 통장 잔액을 출력해야 하므로 point query로 볼 수 있다. 그렇다면 만약 이 문제에서 명령 1을 연속된 어떠한 구간 [A, B]에 대한 range update로 변경할 수 있다면, 느리게 갱신되는 세그먼트 트리(lazy propagation)를 적용하거나 range update - point query 펜윅 트리를 통해 풀 수 있다. 내 경우엔 펜윅트리로 풀었다. 이 글에서 필요한 개념을 익히려면 적어둔 펜윅트리 글에서 응용2 부분을 이해해보자.

 

  명령1을 [A, B] 구간에 대한 range update로 변경하는 과정은 오일러 경로 테크닉을 통해 구할 수 있다. 1번 노드부터 시작해서 dfs를 돌려주면서 새로 만나는 노드 순서대로 번호를 붙여주면 된다. 그게 [A, B]에서 A에 해당한다. 그리고 재귀적으로 구현했을 때, 자신을 통해 시작된 재귀함수가 생성하는 최대 A값이 B에 해당하게 된다. 물론 해당 노드에서 진행 가능한 간선이 여러개라면 어딜 먼저 가더라도 상관없다. 과정은 다음과 같이 된다.

 

 

 

---

 

코드 : github

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

public class Main {
    int n, num = 1;
    int[] bit, mapping, rangeEnd;
    ArrayList<Integer>[] sub;

    private int query(int idx) {
        idx = mapping[idx];
        int sum = 0;
        while (idx > 0) {
            sum += bit[idx];
            idx -= idx&-idx;
        }
        return sum;
    }

    private void update(int idx, int diff) {
        while (idx <= n) {
            bit[idx] += diff;
            idx += idx&-idx;
        }
    }

    private void rangeUpdate(int s, int e, int diff) {
        update(s, diff);
        update(e+1, -diff);
    }

    private void rangeUpdate(int idx, int diff) {
        int s = mapping[idx];
        int e = rangeEnd[s];
        if (e == 0)
            return;
        rangeUpdate(s, e, diff);
    }

    private int initNumAndRange(int idx) {
        int end = (mapping[idx] = num++);
        if (sub[idx] == null)
            return rangeEnd[end] = end;

        for (int next : sub[idx]) {
            end = initNumAndRange(next);
        }
        rangeEnd[mapping[idx]] = end;
        return end;
    }

    private void init(int n) {
        this.n = n;
        sub = new ArrayList[n+1];
        mapping = new int[n+1];
        rangeEnd = new int[n+1];
        bit = new int[n+1];
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        init(Integer.parseInt(st.nextToken()));
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        st.nextToken();
        for (int i = 2; i <= n; i++) {
            int cur = Integer.parseInt(st.nextToken());
            if (sub[cur] == null)
                sub[cur] = new ArrayList<>();
            sub[cur].add(i);
        }

        initNumAndRange(1);

        StringBuilder sb = new StringBuilder();
        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            switch (st.nextToken().charAt(0)) {
                case '1':
                    rangeUpdate(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
                    break;
                case '2':
                    sb.append(query(Integer.parseInt(st.nextToken()))).append('\n');
            }
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}