[백준] 14929 귀찮아 (SIB) - 누적합(Prefix Sum) JAVA

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

14929번: 귀찮아 (SIB)

코드설명

누적합 문제입니다.

 

PrefixSum[N] 이란 N번쨰 인덱스까지의 합을 의미합니다.

미리 prefixSum을 구함을 통해 우리는 합 계산을 매번 구하지 않아도 됩니다.

 

문제의 그림을 보면 1<=a<b<=n 으로 시그마의 범위가 정해져있습니다. 해당 계산식에 맞게 해결하면됩니다.

예시를 그려보면,

x1(x2+x3) + x2(x3) 이 됩니다.

 

arr과 prefixSum 값을 표로 나타내보면,

arr

Index	0	1	2
Value	+1	-2	+3

 

prefixSum

Index	0	1	2	3
Value	0	+1	-1	+2

여기서 x2 + x3 을 구하려면 PrefixSum[3] - PrefixSum[2-1] 을 하면 1이 나옵니다. 

PrefixSum[3] 은 arr[0] 부터 arr[2]까지의 전체 합을 의미하고, PrefixSum[1]은 arr[0]까지의 합을 의미합니다. 그러므로 arr[1] + arr[2]의 값이 나옵니다.

 

문제조건에, N은 10만 까지 가능하기에,

만약 값이 10만개로  입력되고, X의 최대값인 100으로 모든 값이 입력된다면, int 형의 범위가 넘어갑니다. 

long 형으로 answer를 해줘야 자료형의 범위에 맞습니다.

 

문제에서 조금 헷갈릴 수 있는점은, arr과 prefixSum의 인덱스가 살짝 다릅니다.

prefixSum은 각 자리에서의 합을 의미하므로 N+1 만큼의 Size입니다.

즉, arr[0]까지의 누적합을 구하려면 prefixSum[0 + 1] 을 구해야합니다.

만약 arr[2]까지의 누적합을 구하려면 prefixSum[2 + 1] 을 구해야합니다.

또한, arr[1] + arr[2]의 합을 구하려면, arr[3] - arr[1] 을 구하면 됩니다.

코드

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


public class Main {
	
	public static int N;
	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());
    	arr = new int[N];
    	prefixSum = new int[N+1];
    	st = new StringTokenizer(br.readLine());
    	
    	int sumValue = 0;
    	for(int i=0;i<N;i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        	
        	sumValue += arr[i];
        	prefixSum[i + 1] = sumValue;
    	}
    	
    	
//    	for(int i=0;i<N+1;i++) {
//    		System.out.println(" "+prefixSum[i]);
//    	}
    	for(int i=0;i<N;i++) {
    		int standard = arr[i];
    		int calculatedSum = prefixSum[N] - prefixSum[i+1];
//    		System.out.println("standard:"+standard+" calcul"+calculatedSum);
    		answer += standard * calculatedSum;
    	}
    	
    	System.out.println(answer);
    	
    }
}