[백준] 11659 구간 합 구하기 4 - 누적합(Prefix Sum) JAVA

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

11659번: 구간 합 구하기 4

코드설명

누적합 문제입니다.

 

누적합을 그대로 구현하면됩니다.

2에서 5까지의 구간합을 구하려고한다면,

prefixSum[5] - prefixSum[1] 을 구해야 2~5까지의 합이 나옵니다.

 

코드

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

public class Main {
	public static int N, M;
	public static int[] arr;
	public static int[] prefixSum;
	public static long answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	

    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    		
    	int sumValue = 0;
    	prefixSum = new int[N+1];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		sumValue += Integer.parseInt(st.nextToken());
    		prefixSum[i+1] = sumValue;
    	}
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		
    		System.out.println(prefixSum[b] - prefixSum[a-1]);
    	}
    
//    	System.out.println(answer);
    }
    
    
}

 

누적합을 다르게 구현해본 코드입니다.

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

public class Main {
    private static int N, T, K, M;
    private static int answer = 0;
    private static int[] arr;
    private static int[] prefixSum;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		prefixSum = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			prefixSum[i] = (i == 0) ? arr[i] : arr[i] + prefixSum[i-1];
		}
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int lo = Integer.parseInt(st.nextToken());
			int hi = Integer.parseInt(st.nextToken());
			
			int loSum = (lo - 1) == 0 ? 0 : prefixSum[lo - 1 - 1];
			int hiSum = prefixSum[hi - 1];
			
			System.out.println(hiSum - loSum);
		}
		
		
    }
    
    
    
}