[알고리즘] Java / 백준 / 구간 합 구하기 5 / 11660

[알고리즘] Java / 백준 / 구간 합 구하기 5 / 11660

문제

문제 링크

접근 방식

1. 행 별로 각 행의 왼쪽에서부터 오른쪽으로의 누적 합을 저장한다
2. sum 변수를 0으로 초기화한 후 x1 행부터 x2행 까지 각 행의 y2 에 위치하는 누적 합에서 y1 -1 에 위치하는 누적 합을 뺀 값을 sum 변수에 더한다

코드

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

public class Main_11660 {

	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 pSum[][] = new int[N+1][N+1];
		
		for(int i=1;i<=N;i++) {
			st=  new StringTokenizer(br.readLine());
			for(int j=1;j<=N;j++) {
				pSum[i][j] = pSum[i][j-1] + Integer.parseInt(st.nextToken());
			}
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(int m=0;m<M;m++) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			
			int sum = 0;
			
			for(int i=x1;i<=x2;i++) {
				sum += pSum[i][y2] - pSum[i][y1-1];
			}
			
			sb.append(sum+"\n");
		}
		
		System.out.print(sb);
	}

}