[백준]11660번 구간 합 구하기 5(JAVA)

0. 문제 링크

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

11660번: 구간 합 구하기 5

 

1. 문제 설명

1) M개의 줄에 입력으로 주어진 (x1, y1)부터 (x2, y2)까지 합 출력하기

 

2. 입출력

// input
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

// output
27
6
64

 

3. 코드

import java.awt.Point;
import java.io.*;
import java.util.*;

public class b11660 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 표의 크기
		int M = Integer.parseInt(st.nextToken()); // 합을 구해야 하는 횟수
		int[][] map = new int[N][N];
		int[][] sumMap = new int[N][N];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int temp = 0;
			for(int j = 0; j < N; j++) {
				temp += Integer.parseInt(st.nextToken());
				sumMap[i][j] = temp;
			}
		}
		
		for(int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			Point x = new Point(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1);
			Point y = new Point(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1);
			
			int sum = 0;
			for(int i = x.x; i <= y.x; i++) {
				sum += sumMap[i][y.y];
				if(x.y-1 >= 0) {
					sum -= sumMap[i][x.y-1];
				}
			}
			
			sb.append(sum + "\n");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

}

 

실행 결과

 

4. 회고

1) 최대 100,000번의 합을 구해야 하므로 열 별로 구간 합을 이용하여 시간 초과를 해결

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Baekjoon/b11660.java