[JAVA] 백준 q11659 - 구간 합 구하기 4

11659번: 구간 합 구하기 4

 

의식의 흐름

구간 합이 뭔지 제대로 공부 안하고 무작정 풀어보기 -> (시간제한 안보고) 그냥 인덱스로 for문 돌리면 되는데 왜 실버지? -> 시간초과ㅎ...

 

풀이

1. 부분 합 배열 만들기

2. 인덱스 받아서 부분 합 적절하게 사용하기

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 수의 개수
        int M = Integer.parseInt(st.nextToken()); // 합을 구해야 하는 횟수
        int[] sums = new int[N+1]; // 합 배열
        int sum = 0;

        st = new StringTokenizer(br.readLine());
        for(int i=1;i<=N;i++){
            sum += Integer.parseInt(st.nextToken());
            sums[i] = sum;
        }

        while(M>0){
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            bw.write(Integer.toString(sums[j]-sums[i-1])+"\n");
            M--;
        }

        bw.flush();

        br.close();
        bw.close();
    }
}

 

알고리즘 정리

[알고리즘] 구간 합 (Prefix Sum)