[BaekJoon 11660번 / JAVA] 구간 합 구하기5

Question

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

11660번: 구간 합 구하기 5

 

---

💡 Solution

DP를 이용하여 해결합니다. 자신이 위치하는 행의 맨 앞 값부터 자신까지를 더하는 누적합을 구하고, 이를 이용하여 문제를 해결합니다.

 

💻 Code

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

public class BJ11660 {
	static int[][] dp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		dp = 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++) {
				//(i, 1)부터 자신의 위치까지의 누적합을 계산
				dp[i][j] = dp[i][j - 1] + Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i = 0; i < M; i++) {
			int result = 0;
			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());
			
			for (int j = x1; j <= x2; j++) {
				result += dp[j][y2] - dp[j][y1 - 1];
			}
			sb.append(result + "\n");
		}
		
		System.out.println(sb.toString().trim());
	}

}