[백준] 11660 - 구간 합 구하기 5(Java)

[백준] 11660 - 구간 합 구하기 5(Java)

문제

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

풀이/후기

예전에 softeer에서였나?

구간합 구하는 문제 풀었을 때와 유사한 문제였던 것 같다.

배열을 입력받을 때부터 누적합을 저장해 두고

원하는 위치의 마지막 점 + (시작점-1) 을 행별로 더해주면 된다.

말보다 소스코드로 이해하는 것이 더 쉽다.

 

오랜만에 바로 문제를 풀어내니 다시 자신감이 생긴다@

코드

package DynamicProgramming;

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

public class Problem11660 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(str.nextToken());
		int M = Integer.parseInt(str.nextToken());
		
		int[][] add = new int [N+1][N+1];
		
		for (int i=1; i<N+1; i++) {
			str = new StringTokenizer(br.readLine(), " ");
			for (int j=1; j<N+1; j++) {
				add[i][j] = Integer.parseInt(str.nextToken()) + add[i][j-1];
			}
		}
		
		for (int i=0; i<M; i++) {
			str = new StringTokenizer(br.readLine(), " ");
			int px = Integer.parseInt(str.nextToken());
			int py = Integer.parseInt(str.nextToken());
			int nx = Integer.parseInt(str.nextToken());
			int ny = Integer.parseInt(str.nextToken());
			
			int sum = 0;
			for (int a = px; a <= nx; a++ ) {
				sum += add[a][ny] - add[a][py-1];
			}
			sb.append(sum).append("\n");
		}
		
		System.out.println(sb);
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/7c4eddb76db1bd7bc9a9000ab0f563d8b282e939

참고