백준 11660번 - 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

 

 

 

 

 

열심히 종이에 그려가면서 구하려고 했는데 너무 복잡하게 생각한 탓인지 못풀었다. 결국 해설을 듣고 알게되었는데, 내가 처음에 잠깐 생각한 '행별로 누적합 구해서 더하기'가 맞았다. 시간초과날 것 같아서 안해봤는데..

 

시간초과 각오하고 시도해보는 것도 좋을 것 같다라는 생각이 들었다. 괜히 시간초과 날 것 같다고 다른 방법 생각하다가 더 복잡하게 생각하고 시간만 더 까먹었다.

 

 

 

 

 

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] dp = new int[N + 1][N + 1];
		
		for(int i = 1; i < N + 1; i++) { //행별 누적 합 저장
			st = new StringTokenizer(br.readLine());
			
			dp[i][1] = Integer.parseInt(st.nextToken());
			
			for(int j = 2; j < N + 1; j++) {
				dp[i][j] = dp[i][j - 1] + Integer.parseInt(st.nextToken());
			}
		}
		
		StringBuilder sb = new StringBuilder();
		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 += dp[j][y2] - dp[j][y1 - 1];
			}
			
			sb.append(sum + "\n");
		}
		
		System.out.println(sb);
	}

}

 

 

 

 

 

결과