[백준 11659] 구간합

🛎 11659 구간합

|  문제 

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

|  입력

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

|  출력

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

|  예제 입력

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

|  예제 출력

12
9
1

 

🔎 문제분석

이 문제를 반복문으로 풀려고 했을 때, 계속적으로 시간초과가 나타났다.

입출력을 내가 아는 모든 방법을 총동원해서 변경해보았지만 역부족.

'뭐지, 풀 수 없는 문제인가' 했었는데, 그게 아니라 이 문제를 푸는 다른 방법이 있어서였다.

 

※ 구간합을 구하는 방법

[1] 먼저, 둘째줄에서 받은 N개의 수들을 arr배열에 넣어준다.

[2] arr배열을 토대로 합배열을 별도로 만든다.

인덱스	0	1	2	3	4
arr	5	4	3	2	1
hap	5	9	12	14	15

[3] 구간 (x1, x2)가 있다고 할 때, 구간의 합을 구하는 방법은 다음과 같다.

1) 만약 x1이 1이라면 : 인덱스 0 부터 x2-1까지의 누적합을 구하는 것이므로 그냥 hap[x2-1]를 반환하면 된다.

2) 만약 x1이 1보다 크면 : 예를들어 (2, 5)라고 할때

    >> 실제 인덱스 범위는 1~4일 것이다.

    hap[4] = arr[0] + arr[1] + arr[2] + arr[3] + arr[4]

    hap[1] = arr[0] + arr[1]

    -----------------------------------------------------------------------------------

    hap[1~4] = arr[1] + arr[2] + arr[3] + arr[4]    <------- 구하려는 값

    >> 구하려는 값이 나오기 위해서는 실제 인덱스 범위는 결국 (x1-2, x2-1)일 것이다.

 

이제 위 원리는 바탕으로 코드를 만들면 다음과 같다.

 

⌨️ 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Ex11659 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(st.nextToken()); //수의 개수
        int M = Integer.parseInt(st.nextToken()); //합을 구해야 하는 횟수

        // 입력받은 수 배열
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            arr[i] = num;
        }

        // 합 배열을 구한다
        int[] hap = new int[N];
        for (int i = 0; i < N; i++) {
            if (i == 0) {
                hap[i] = arr[i];
                continue;
            }
            hap[i] = hap[i - 1] + arr[i];
        }

        // 구간합을 구한다.
        for (int i = 0; i < M; i++) {

            st = new StringTokenizer(br.readLine());

            int x1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());

            int sum = 0;
            if (x1 == 1) {
                sum = hap[x2 - 1];
            }else {
                sum = hap[x2 - 1] - hap[x1 - 2];
            }

            bw.write(String.valueOf(sum));
            bw.write("\n");

        }
        
        bw.flush();
        bw.close();
        
    }
}