[백준] G1 2042 구간 합 구하기 (java)

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

2042번: 구간 합 구하기

 

풀이

 

1) 구간 합 배열(sum[])을 만든다. sum[i] : 0 부터 i 까지의 합.

2) a가 1 일 경우
  2-1) 변경된 숫자의 번호와 차이값을 List에 저장한다. (인덱스, c - arr[i])

3) a가 2 일 경우
  3-1) 숫자 변경을 배제한다면 b~c 의 구간합은 sum[c] - sum[b-1]
  3-2) list를 순회하며 b~c 구간에 변경된 값들이 있다면 그 값을 모두 temp에 더하기
  3-3) 3-1 과 3-2를 더해서 출력

 

 

주의사항

 

1) sum 배열을 매번 고치려면 무적권 시간초과.

2) 해보진 않았지만 K가 최대 10000 이라서 System.out 을 쓰면 시간이 오래 걸릴듯? BufferedWriter ㄱㄱ

3) 범위 주의 (long)

 

package com.baekJoon;

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BJ_G1_2042_구간합구하기 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer tokens;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        tokens = new StringTokenizer(input.readLine());
        int N = Integer.parseInt(tokens.nextToken());
        int M = Integer.parseInt(tokens.nextToken());
        int K = Integer.parseInt(tokens.nextToken());

        long arr[] = new long[N+1];
        long sum[] = new long[N+1];
        for(int i=1; i<N+1; i++){
            arr[i] += Long.parseLong(input.readLine());
        }
        sum[1] = arr[1];
        for(int i=2; i<N+1; i++){
            sum[i] = sum[i-1] + arr[i];
        }

        List<Node> list = new ArrayList<>();
        for(int i=0; i<K+M; i++){
            tokens = new StringTokenizer(input.readLine());
            long a = Long.parseLong(tokens.nextToken());
            long b = Long.parseLong(tokens.nextToken());
            long c = Long.parseLong(tokens.nextToken());

            if(a == 1){
                list.add(new Node((int)b, c - arr[(int)b]));
                arr[(int)b] = c;
            }else{
                long temp = 0;
                for(int j=0; j<list.size(); j++){
                    if(list.get(j).idx >= b && list.get(j).idx <=c){
                        temp += list.get(j).num;
                    }
                }
                output.append(sum[(int)c] - sum[(int)b-1] + temp +"\n");
            }
        }
        output.close();
    }

    static class Node {
        int idx;
        long num;

        public Node(int idx, long num) {
            this.idx = idx;
            this.num = num;
        }
    }

    static String src =
            "5 2 2\n" +
                "1\n" +
                "2\n" +
                "3\n" +
                "4\n" +
                "5\n" +
                "1 3 6\n" +
                "2 2 5\n" +
                "1 5 2\n" +
                "2 3 5";
}

 

 

후기

 

 누적합으로 다 풀고보니 세그먼트 트리문제였다. 어쩐지 메모리, 시간이 저모양이더라..

문제에서 모든 입력값은 -2^64 ~ 2^64 인데 중간에 (1 ≤ b ≤ N) 요런놈이 있어서 헷갈렸다. 그냥 a가 1 일때와 2 일때를 구분해서 확실히 알려줬으면 좋겠다.

스터디 난이도를 G2~G1 로 고른다는데 맨날 G1만 푸는거 같은건 기분탓인가..?