백준 P11659_구간합구하기

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

예제 입력 1 복사

5 3
5 4 3 2 1
1 3
2 4
5 5

예제 출력 1 복사

12
9
1

 

 

 

 

답

package baekjoon;

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

public class P11660 {
    public static void main(String[] args)throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer=new StringTokenizer(bufferedReader.readLine());
        int suNo = Integer.parseInt(stringTokenizer.nextToken());
        int quizNo = Integer.parseInt(stringTokenizer.nextToken());
        long [] S = new long [suNo+1];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for(int i =1;i<=suNo;i++){
            S[i]=S[i-1]+Integer.parseInt(stringTokenizer.nextToken());
        }
        for(int q=0;q < quizNo;q++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int i =Integer.parseInt(stringTokenizer.nextToken());
            int j =Integer.parseInt(stringTokenizer.nextToken());
            System.out.println(S[j]-S[i-1]);
        }
    }
}

풀이

1. 사용자로부터 배열의 크기(N)와 쿼리의 수(quizNo)를 입력받는다.
2. 배열 S를 선언하여 각 행의 누적합을 저장한다. 이를 위해 첫 번째 행은 0으로 초기화한다.
3. 사용자로부터 배열의 각 요소를 입력받으면서 각 행의 누적합을 계산하여 배열 S에 저장한다.
4. 각각의 쿼리에 대해 해당 구간의 부분합을 계산하여 출력한다.

느낀점

 

이 문제를 해결하는 데에 있어서는 입력 처리를 위해 BufferedReader와 StringTokenizer를 사용하여 성능을 향상시켰습니다. 또한, 누적합을 활용하여 각 쿼리의 답을 빠르게 계산할 수 있습니다.