[누적합] 백준 - 구간 합 구하기 4

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

-문제해설

그냥 주어진 i와 j인덱스를 반복문으로 돌면서 구간 합을 구할 경우 시간초과가 나오게 된다.

따라서 애초에 데이터를 배열에 집어넣을 때 첫 번째 인덱스부터 삽입되는 인덱스까지의 누적 합을 구한 뒤 배열에 집어넣고 i부터 j까지의 구간합을 구하는 방법은 다음과 같다.

 

arr[ j ] - arr[ i-1 ] 

 

예를 들어서 배열 5 4 3 2 1 이 있을 때 2번 인덱스부터 4번 인덱스까지의 구간합을 구한다고 할 경우

정답은 4 + 3 + 2 = 9이다.

 

이때 각 인덱스의 누적합은 다음과 같다.

5 9 12 14 15

이고 14 - 5 = 9가 되므로 정답이 나오게 된다.

 

 

파이썬의 경우 입력은 stdin을 사용해야하고 리스트의 누적합을 구해주는 accumulate 모듈을 사용했다.

 

-자바

package math;

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

public class BJ11659 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() );
		int m = Integer.parseInt( st.nextToken() );
		
		long[] arr = new long[n+1];
		st = new StringTokenizer( br.readLine() );
		long sum = 0;
		for( int i=1; i<=n; i++ ) {
			sum += Integer.parseInt( st.nextToken() );
			arr[i] = sum;
		}
		
		StringBuilder sb = new StringBuilder();
		while( m --> 0 ) {
			st = new StringTokenizer( br.readLine() );
			int a = Integer.parseInt( st.nextToken() );
			int b = Integer.parseInt( st.nextToken() );
			
			sb.append( arr[b] - arr[a-1] ).append( "\n" );
		}
		System.out.println( sb );
	}
}

 

-파이썬

from itertools import accumulate
from sys import stdin

def sol( n, m ):
    tmp = map(int, input().split())
    arr = [0] + list( accumulate( tmp ) )
    
    for _ in range( m ):
        a, b = map(int, input().split())
        print( arr[b]-arr[a-1] )

if __name__ == '__main__':
    input = stdin.readline
    sol( *map(int, input().split()) )