[자바] 백준 11660번: 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

 

2차원 배열을 만들어서

0행,0열은 모두 0으로 채우고,

한 행씩 입력을 받는데

arr[i][j]=arr[i][j-1]+입력받은값 

으로 배열을 채워서, 각 행은 오른쪽으로 가면서 누적합이 기록되게 하였다.

 

이제 x1,y1,x2,y2를 입력받고

for(int i=x1;i<=x2;i++) 반복문을 돌면서 

한 행씩 구간 합을 구하는데,

arr[i][y2]-arr[i][y1-1]로 계산하면 시간복잡도O(1)만에 한 행 안에서의 구간합을 구할 수 있다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

public class P11660 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int[][] arr = new int[n + 1][n + 1];
		// 0행, 0열은 0으로 채움
		for (int i = 0; i <= n; i++) {
			arr[i][0] = 0;
			arr[0][i] = 0;
		}

		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= n; j++) {
				arr[i][j] = arr[i][j - 1] + Integer.parseInt(st.nextToken());
				// 각 행은 누적합을 기록함
			}
		}

		for (int i = 0; i < m; i++) {
			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 j = x1; j <= x2; j++) {
				sum += (arr[j][y2] - arr[j][y1 - 1]);
			}
			//System.out.println(sum);
			bw.append(sum+"\n");
		}
		
		bw.flush();

		bw.close();
		br.close();
	}

}

m의 최댓값은 10만이기 때문에

System.out으로 출력하게되면 10만번 출력해야해서 시간초과가 날 수 있다.

bufferedwriter을 사용하면 된다.