백준 11660 - 구간 합 구하기 5

Java

11660 번 - 구간 합 구하기 5

문제

접근 방법

2차원 배열 누적합을 계산하였다.

현재 위치가 (y,x)라고 할 때, 시작 부터 (y,x)까지 누적합은 현재 위치를 기준으로 [누적합 [위쪽 값 + 왼쪽 값 - 왼쪽,위쪽 값] + 현재 위치 값] 이다.

이후 y1,x1, y2,x2의 범위의 누적합은 [(y2,x2) - (y1 - 1, x2) - (y2, x1 - 1) + (y1 - 1, x1 - 1)] 이다.

이번에 얻은 팁

처음 해결하였을 때는 현재 위치에서 -1을 할 때 배열 범위를 벗어나는지 확인하여야 했지만, 시작점을 1,1부터 두면 0번째 행,열은 자동으로 0으로 계산되어서 편하다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, result;
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("res/mainInput.txt"));	//제출 할 때 주석해야함
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	
    	int[][] arr = new int[n + 1][n + 1];
    	int[][] dp = new int[n + 1][n + 1];		// 행열 기준 4각형 누적 합
    	
    	for(int i = 1; i <= n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 1; j <= n; j++) {
    			arr[i][j] = stoi(stk.nextToken());
    		}
    	}
    	
		// 누적 합 구하기
    	for(int i = 1; i <= n; i++) {
    		for(int j = 1; j <= n; j++) {
    			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];
    		}
    	}
    	// 범위의 값 구하기
    	while(m-- != 0) {
    		int y1, x1, y2, x2;
    		stk = new StringTokenizer(br.readLine());
    		y1 = stoi(stk.nextToken());
    		x1 = stoi(stk.nextToken());
    		y2 = stoi(stk.nextToken());
    		x2 = stoi(stk.nextToken());
    		
    		result = dp[y2][x2] - dp[y1 - 1][x2] - dp[y2][x1 - 1] + dp[y1 - 1][x1 - 1];
    		
    		System.out.println(result);
    	}
    	
    	
    	br.close();
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점