[BOJ] 백준 11441 합 구하기

Approach

출처: https://www.acmicpc.net/problem/11441

 

구간합을 구하는 문제이다.

배열로 원소를 담아서 [s, e] 구간의 합을 구해도 된다.

📌 연속된 부분 합(연속합) - 1 (완전 탐색)

 

Java

import java.util.Scanner;

public class Main {    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = Integer.parseInt(sc.nextLine());
        int[] arr = new int[N+1];
        for(int i=1; i <= N; i++) {
        	arr[i] = Integer.parseInt(sc.next());
        }
        
        int M = Integer.parseInt(sc.next());
        while(M-- > 0) {
        	int start = Integer.parseInt(sc.next());
        	int finish = Integer.parseInt(sc.next());
        	int sum = 0;
        	for(int idx=start; idx<=finish; idx++)
        		sum += arr[idx];
        	System.out.println(sum);
        }       
    }
}

 

구간합을 빠르게 구하는 방법은 누적합을 이용하는 것이다.

입력 값으로 {10, 20, 30, 40, 50} 숫자가 주어졌을 때,

 

psum[i] = i 번째까지의 누적합

→ psum[] = {0, 10, 30, 60, 100, 150}

누적합(psum[])을 쉽게 이용하기 위해서 psum[0] = 0 으로 두었다.

 

<누적합을 이용하는 방법>

만약 [1, 3] 구간합은 = 10 + 20 + 30 = 60 이다.

누적합에서 psum[3] - psum[1 - 1] = psum[3] - psum[0] = 60

다른 예시로 [4, 4] 구간합은 40이다.

psum[4] - psum[4 - 1] = psum[4] - psum[3] = 100 - 60 = 40

 

📌 연속된 부분 합(연속합) - 2 (Prefix Sum)

📌 연속된 부분 합(연속합) - 3 (DP)

 

C++

#include <iostream>

using namespace std;

const int MAX_N = 100000 + 5;
int N, M, psum[MAX_N], val;
int s, e;

int main() 
{
	// freopen("input.txt", "r", stdin);

	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &val);
		psum[i] = val + psum[i - 1];
	}

	// 구간합을 구해야하는 개수(= M)
	scanf("%d", &M);
	while (M--) 
	{
		scanf("%d %d", &s, &e);
		printf("%d\n", psum[e] - psum[s - 1]);
	}
}