[Algorithm] 배열의 합 구하기

이번 문제는 N X M 배열의 합을 구하는 문제다. 그런데 이 때 입력이 어떤 배열의

두 start , end를 지정하면 그 사이 지역에 해당하는 값들의 합을 구하는 문제다.

위 문제를 해결하기 위한 아이디어는 다음과 같았다. 먼저 N개의 행에 대하여 각각의 

해당하는 부분에 대한 부분합을 N개를 구한 후 다 더하게 되면 결과 값이 나오게 된다.

그렇다면 부분합은 어떻게 구할까 ?

이에 대한 해답으로 나는 입력에 대한 누적 합을 배열로 만들었다. 입력이 1 2 4 가 

들어오면 누적합 배열은 1 3 7 이런식으로 생성하였다.

그 후 이것을 이용하여 V[i] ~ V[j] (i 번째 부터 j번째 까지의 부분합)은 D[j] - D[i-1] 을

이용하여 구할 수 있었다.(D는 누적합배열)

예를 들어 , 위와같은 입력이 있을 때 4 ~ 5의 부분합을 구하면 빨간 부분에 해당하고 

이 값은 21 - 7 을 이용하여 구할 수 있다.

위와 같은 방법으로 N개의 부분합을 구하여 더하면 끝 !

개인적으로 일반화된 DP문제를 풀다가 이런 아이디어가 필요한 DP문제를 푸는 것은

두뇌의 환기에 굉장히 좋은 것 같다. 다양하고 많은 문제를 풀어볼 필요가 있다고 느꼈다.

소스코드:

package algorithm;

import java.io.*;

import java.util.*;

public class a_2167 {

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

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine()," ");

int N = Integer.parseInt(st.nextToken());

int M = Integer.parseInt(st.nextToken());

int [][]C = new int[N+1][M+1];

for(int i=1;i<=N;i++){

st = new StringTokenizer(br.readLine()," ");

C[i][0] = C[i-1][M];

for(int j=1;j<=M;j++){

C[i][j] = Integer.parseInt(st.nextToken()) + C[i][j-1];

}

}

int T = Integer.parseInt(br.readLine());

for (int k=0;k<T;k++){

st = new StringTokenizer(br.readLine()," ");

int i = Integer.parseInt(st.nextToken());

int j = Integer.parseInt(st.nextToken());

int x = Integer.parseInt(st.nextToken());

int y = Integer.parseInt(st.nextToken());

int sum = 0;

for (int t = i;t<=x;t++) sum+=C[t][y] - C[t][j-1];

System.out.println(sum);

}

}

}