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

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

11660번: 구간 합 구하기 5

 

 

 

 

 

 

문제

• N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램 작성
• 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000)
• N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다.
• 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

 

 

 

 

 

풀이

 표의 크기인 N의 크기가 최대 1024, 쿼리의 개수인 M이 최대 100,000으로, 합을 구하는 데, 최악의 경우에는 N *N * M = 1024 * 1024 * 100,000 (약 10,000,000,000 = 100억)이 걸린다!

 

 매번 합을 누적해서 계속 더하는 것 보다는, 이전의 합의 결과를 저장 후 이용하면 효율적으로 합을 구할 수 있다. DP를 활용하면 된다.

 

 

 

[방법1] 행 별로 누적 합 저장하기 (1500ms 대)

 

 1년 전에 이 방법으로 이 문제를 풀었다. 행 별로 누적합을 저장하는 DP를 활용하여 1500ms 대의 시간으로 성공을 하긴 했지만, 800ms 대가 나오는 다른 풀이보다는 비효율적인 방법이다.

 

 

1. dp[i][j]로 행 별 누적합 구하기

 

행 별로 dp[i][0]~ dp[i][M] 까지의 누적합을 구해나간다. 

 

 

 

2. (x1, y1)부터 (x2, y2)의 합 구하기

 

 

x1부터 x2까지 dp[i][y2] - dp[i][y1] 의 값을 더해나가면 된다.

 

 

 

 

 

DP를 사용해서 행 별 누적합을 구하는 것은 최적화가 되었지만, 매번 x1부터 x2까지 합을 계산해야 하기 때문에 시간이 오래 걸린다..

 

 

 

 

 

코드

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);
	}

}

 

 

 

 

 

 

 

[방법2] 행렬 전체의 누적 합 저장하기 (800ms 대)

 

매번 행 별로 값을 더하는 시간을 줄이기 위해서는 행 별이 아니라 행렬 전체의 누적합을 저장해야 한다.

 

 

 

1. dp[i][j]로 (1, 1)~(i, j)의 누적합 구하기

 

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j]

 

 

빨간색 부분인 dp[i - 1][j]와 파란색 부분인 dp[i][j - 1]를 더하고, 중복해서 더한 노란색 부분인 dp[i - 1][j - 1]을 빼주고, 자신인 arr[i][j]을 더해준다.

 

 

 

2. (x1, y1)부터 (x2, y2)의 합 구하기

 

(x1, y1)부터 (x2, y2)를 구하는 데는 (1, 1)~(i, j)까지의 누적합인 dp[i][j]를 활용하여 적절히 연산을 하면 된다.

 

 

노란색 부분을 구하기 위해서는 초록색 부분인 dp[x1 - 1][y2]를 빼고, 파란색 부분인 dp[x2][y1 - 1]을 빼주고, 중복해서 뺀 부분인 회색 부분인 dp[x1 - 1][y1 - 1] 을 더해주면 된다.

 

 

 

 

 

코드

import java.io.*;
import java.util.*;

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[][] arr = new int[N + 1][N + 1];
		
		for(int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 1; j <= N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int[][] dp = new int[N + 1][N + 1]; //행렬 (i, j)까지의 합
		
		//행렬 (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];
			}
		}
		
		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 answer = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
			sb.append(answer).append("\n");
		}
		
		System.out.println(sb);
	}

}

 

 

 

 

 

결과

 

800ms대 : 방법2

1500ms대 : 방법1

 

 

 

 

 

배운점