[백준] 2268.수들의 합 7 - 세그먼트트리(JAVA)

문제링크 🚩

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

 

​

📕 문제 접근 📕

• 해당 문제는 세그먼트 트리에서 트리를 만드는 과정에 없어지고 modify와 sum만하면 풀 수 있도록 만들어진 문제다
• 세그먼트 트리의 정석적인 풀이 방법대로 풀면 매우 쉽지만 문제를 잘 읽어야한다.
• • N개의 수 A[1], A[2], …, A[N] 이 주어졌을 때, 함수 Sum(i, j)는 A[i] + A[i+1] + … + A[j]를 구하는 함수이다. (i > j일 경우에는 A[j] + A[j+1] + ... + A[i]) A가 주어졌을 때**
• 해당 조건을 확인하면 i > j 일 때 도 있다는 의미가 내포되어있다. 해당 부분을 놓친다면 답이 틀리게된다.

💻 Code 💻

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_2268 {
    /**
     *  0 -> sum   i, j -> 의합
     *  1 -> modify -> i번째를 K로 바꾸는 수식
     *  처음배열은 전부 0으로 세팅
     *
     */
    static int N, M;
    static long  tree[];

    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st =new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());


        tree = new long[N*4];

        for(int i = 0 ; i < M ; i ++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken()) ;
            int c = Integer.parseInt(st.nextToken()) ;
//            System.out.println("Arrays.toString(tree) = " + Arrays.toString(tree));
            if(a == 0){
                //sum
                if (b > c) {
                    int temp = b;
                    b = c;
                    c = temp;
                }
                sb.append(sumTree(1, N, 1, b, c) + "\n");
            }else if (a == 1){
                //modify
                modifyTree(1, N, 1, b, c);
            }
        }
        System.out.println(sb.toString());
    }


    private static long sumTree(int start, int end, int node, int left, int right){
        if(left > end || right < start ){
            return  0;
        }


        if(left <= start && end <= right){
            return tree[node];
        }

        int mid = (start + end) /2;

        return sumTree(start, mid , node *2 , left,right) + sumTree(mid + 1, end, node *2 +1, left,right);
    }
    private static long modifyTree(int start, int end, int node, int target, int num){
        if(target < start || target > end){
            return tree[node];
        } // 인덱스가 범위를 벗어나면 현재값 리턴

        if(start == target && end == target){ // 시작값하고 target이 맞을 때 end가 target하고 맞을 때만 들어옴
            return tree[node] = num;
        }

        int mid = (start + end) /2;

        return tree[node] = modifyTree(start , mid , node *2 , target, num) + modifyTree(mid + 1, end, node * 2 + 1, target, num);
    }

}

💻 Code Review**💻**

 

 

 

📖 배운점 📖

- 조건을 빠짐없이 잡아두고 문제를 풀어야한다는 것을 배웠다.

- 대부분 조건에 명시가 되지만 해당 문제는 글 내에서 조건을 내포하고 있었기에 습관처럼 그냥 넘어가 틀렸던 문제인 것 같다.