[PS] BOJ11659 구간합구하기4 ( prefix-sum ) with Python,JAVA

◎ 문제

11659번: 구간 합 구하기 4

 

◎ 문제풀이

 

구간합을 구하는 문제이다. 시간제한이 1초이다.

 

대략 연산횟수 1억~10억이 1초가 걸린다. 반복문을 이용하면 시간복잡도는 O(N)이다. N은 최대 크기는 10만이다. 구간합을 M번 구해야 한다. 고로 N x M 연산해야 한다. 시간복잡도는 O(NM)이다.  M도 10만이 최대이므로 최대 100억번의 연산을 수행해야 한다. 

 

반복문을 활용하면 시간제한에 걸린다. 그러니 prefix-sum 알고리즘을 활용해보자. prefix-sum(누적합) 알고리즘은 초기화 할때, O(N) 시간복잡도로 수행되고 합을 구할때는 O(1) 시간복잡도로 구현된다. prefix-sum 알고리즘은 미리 누적합을 자료구조에 넣어두어 부분합을 구할 때 시간복잡도를 줄이는 원리이다.

 

수열에 3번째 4번째 사이의 구간합을 구하고 싶다. 

 

3번째 4번째 사이의 구간합 = 4까지 누적합 - 2까지 누적합

 

 

 

i ~ j 의 구간합을 구하고 싶으면 j의 누적합 - (i-1) 누적합을 구하면 된다. 

 

 

◎ 문제풀이

 

Python

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
arr = list(map(int,input().split()))
sum = [0]*(n+1)

for i in range(1,n+1) :
  sum[i] = sum[i-1] + arr[i-1] 

for _ in range(m) : 
  i,j = map(int,input().split())
  result = sum[j] - sum[i-1]
  print(result)

 

JAVA

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


public class PrefixSum1 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st1.nextToken());
        int m = Integer.parseInt(st1.nextToken());

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int[] arr = new int[n+1];
        int[] sum = new int[n+1];

        arr[1] = Integer.parseInt(st2.nextToken());
        sum[0] = 0;
        sum[1] = arr[1];

        int i = 2;
        while(st2.hasMoreTokens()){
            arr[i] = Integer.parseInt(st2.nextToken());
            sum[i] = sum[i-1] + arr[i];
            i++;
        }

        while(m-- > 0){
            StringTokenizer st3 = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st3.nextToken());
            int b = Integer.parseInt(st3.nextToken());
            System.out.println(sum[b]-sum[a-1]);
        }
    }
}