이것저것 개발 블로그

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

문제)

풀이)

바로 직전 문제를 풀면 이것도 누적합을 구해야 하겠거니~~ 는 알 것이다.

안 그럼 바로 시간초과!!

크게 두 가지로 푸는 것 같다.

첫 번째는 내가 푼 것과 같이 한 행을 기준으로 구간합을 구하고, y1 이전까지 더한 구간 합을 빼는 것이다!

그리고 그 행을 x1부터 x2까지 더해주면 끝!

이때, 입력값을 용이하게 사용하기 위해 배열은 [N+1][N+1]의 이차원 배열로 선언했다.

코드를 보면 알겠지만, 이렇게 해도 시간 초과가 나와서, 최대한 시간을 줄이기 위해 노력했다.

bufferedreader, stringbuilder를 사용하여 입력, 출력 모두 시간 단축을 했다!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//import java.util.Scanner;

public class Main_BJ_11660_구간합구하기5 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		//Scanner sc = new Scanner(System.in);
//		int N = sc.nextInt();
//		int M = sc.nextInt();
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] arr = new int[N+1][N+1];
		for(int i=1; i<N+1; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<N+1; j++) {
				//arr[i][j] = arr[i][j-1]+sc.nextInt();	//행별로 누적합
				arr[i][j] = arr[i][j-1] + Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<M; i++) {
//			int x1 = sc.nextInt();
//			int y1 = sc.nextInt();
//			int x2 = sc.nextInt();
//			int y2 = sc.nextInt();
			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 k=x1; k<=x2; k++) {
				//y2있는곳까지 누적합 - y1 전 위치까지 누적합 => 각 행마다 반복
				sum+=arr[k][y2]-arr[k][y1-1];
			}
			sb.append(sum + "\n");
			//System.out.println(sum);	
		}
		System.out.println(sb);	//시간초과 없애기..
		//sc.close();

	}

}

두 번째 방법은 DP를 사용한, 구글링을 하면 많이 나오는 방법이다.

https://subbak2.com/m/65

이 분의 글을 보고 이해했다.

그림 잘 그려주셔서 이해가 쉬웠다!

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

public class Main_BJ_11660_구간합구하기5_2 {

	static int[][] arr; // 입력 배열
	static int[][] dp; // dp [i][j] = (1,1)에서 (i,j) 까지의 합

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
        //입력
		arr = new int[N+1][N+1];
        dp = new int[N + 1][N + 1];
		for(int i=1; i<N+1; i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j=1; j<N+1; j++){
            	arr[i][j] = Integer.parseInt(st.nextToken());
            }
          }

		// DP: dp[i][j] = (1,1)에서 (i,j)까지의 합
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				// (왼쪽← 값) + (위에↑ 값) - (↖중복되는 대각선 값) + (인풋값)
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];
			}
		}

		// 정답 구해서 출력
		int x1, y1, x2, y2;
		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			x1 = Integer.parseInt(st.nextToken());
			y1 = Integer.parseInt(st.nextToken());
			x2 = Integer.parseInt(st.nextToken());
			y2 = Integer.parseInt(st.nextToken());

			sb.append((dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]) + "\n");
		}
		System.out.println(sb);
	}
}