[🧠 Do it! 알고리즘] 2-2. 구간 합

🧠 목차

1. 구간 합
2. [실전 문제] 구간 합 구하기 4 (백준 11659)

---

1. 구간 합

• 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
• 코딩 테스트에서 사용빈도가 높다.

 

합 배열

• 배열 A가 있을 때 합 배열 S 정의

S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]   // A[0]부터 A[i]까지의 합

 

합 배열 S를 만드는 공식

S[i] = S[i -1] + A[i]

 

 

구간 합을 구하는 공식

S[j] - S[i-1]    // i 에서 j 까지 구간 합

 

---

2. [실전 문제] 구간 합 구하기 4 (백준 11659)

문제: 구간 합 구하기 4 https://www.acmicpc.net/problem/11659

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int numN = sc.nextInt();
        int psN = sc.nextInt();

        int[] s = new int[numN + 1];

        for(int i = 1; i <= numN; i++) {
            int num = sc.nextInt();
            s[i] += s[i - 1] + num;
        }

        for(int i = 0; i < psN; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            System.out.println(s[b] - s[a - 1]);
        }

        sc.close();
    }
}