백준 11660 java - 구간 합 구하기 5(누적합)

문제, 입출력, 테스트케이스

이거 시간초과 나야 정상인 것 같은데 시간 초과가 애매하게 안났다. 1초 제한인데 최악 1,024 x 100,000이라서 102,400,000회=> 1초 될랑말랑이라 간당간당했나보다. 그냥 한 번 돌려봤는데 통과되서 놀랬다...!

사실 이러면 안되는 게 될까 말까가 아니라 이건 된다라는 마음으로 문제풀어야하는데... 요행을 바라는 건 실력이 아니다! ㅜ.ㅜ

<문제 풀이/접근과정>
1. 각 행 별로 누적합을 구해둔다.
2. 테스트 케이스 상 x좌표가 배열의 행좌표, y좌표가 열좌표이므로 헷갈리지 말자 -> 1트에 실패했음
3. 행별 구간합을 구해서 더 해준다. -> 소스코드 참조

<소스코드>

package boj;

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

public class Boj_11660 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stz.nextToken());
		int M = Integer.parseInt(stz.nextToken());
		
		int sum[][] = new int[N+1][N+1];
		
		for (int i = 1; i <= N; i++) {
			stz = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				sum[i][j] = sum[i][j-1] + Integer.parseInt(stz.nextToken());
			}
		}
		StringBuilder sb = new StringBuilder();
		// (x1, y1), (x2, y2)
		for (int i = 0; i < M; i++) {
			stz = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(stz.nextToken()); 
			int y1 = Integer.parseInt(stz.nextToken()); 
			int x2 = Integer.parseInt(stz.nextToken()); 
			int y2 = Integer.parseInt(stz.nextToken());
			long tempSum = 0;
			for (int j = x1; j <= x2; j++) {
				tempSum += sum[j][y2] - sum[j][y1-1]; 
			}
			sb.append(tempSum).append("\n");
		}
		sb.setLength(sb.length()-1);
		System.out.println(sb);
	}
}