[ALGO#10] 백준_11660_실버1_구간 합 구하기5 : 구간합, DP [JAVA]

문제 링크

11660번: 구간 합 구하기 5

 

이 문제를 풀기전 구간 합 구하기 4를 꼭 풀기바랍니다.

구간 합 구하기 4가 1차원 배열이라면 이번 문제는 2차원 배열 구간합 문제입니다. 

 

 

시간 초과

이 문제를 입력 값을 살펴보면 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다.
(1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000)  (제한 시간 1초)
매번 구간합을 구하면 N^2(1024*1024) * M (10만)으로 빅오에서 시간 초과가 발생할 수 있습니다.
처음엔 행만 구간합을 구했는데 시간초과가 떠서 행과 열의 구간합을 구해서 풀었습니다. 또한 StringBuilder로 시간을 절약했습니다. 시간 초과가 안뜨려면 횟수 100,000일 때 바로 값이 나오는 O(M) 으로 풀어야 합니다. 따라서 바로 누적합이 계산되어있는 방향으로 풀어야 합니다. 

누적합은 두 단계로 나누어진다.
1. 전처리: 누적합 배열 S를 구한다.
일차원 누적합은 O(n), 이차원 누적합은 O(n^2) 시/공간 복잡도를 갖는다.
2. 계산: 원하는 구간의 구간합을 계산한다.
차원 관계없이 O(1)의 상수 시간 복잡도를 갖는다.

 

 

DP

DP 방법으로 규칙을 찾아 요소 값을 식으로 세웠습니다.
누적되는 구간에서 어떤 값이 중복되는 값인지 파악하기 (중복된 값을 누적 값에서 빼주기)

 

주의

1. 누적합의 한계는 누적합의 경우 합을 구하는 도중에 원본 배열이 변하는 경우 누적합을 다시 계산해야 한다. 이 경우에는 세그먼트 트리를 사용해야한다. 

2. 또한 누적합의 최대값이 int의 범위를 초과하는지 확인해야한다. 

 

Tip

누적합 같은 문제는 입력 값이 대부분 값이나 좌표가 1부터 주어져서 누적 배열도 0 인덱스를 비우고 1부터 값 처리를 해주는 것이 수월합니다. 저는 이 문제 풀 때 0 행과 열은 비워서 for문이나 DP식에서 수월하게 풀 수 있었습니다.

 

 

성능 요약

메모리: 71432 KB, 시간: 1976 ms

 

분류 : 누적 합(prefix_sum)

 

전체 코드 (JAVA)

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

public class BOJ_S1_11660_구간합구하기5_sol {
	
	static int sum;
	static int[][] map;
	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()); //구하는 횟수
	
	// 0번 인덱스를 비우면서 예외처리를 쉽게 하기 위해서
	int[][] map = new int[N+1][N+1];
	int[][] sums = 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++) {
				// (1,1)부터 초기화
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
	// 배열 요소 누적합 초기화
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				sums[i][j] = sums[i][j-1] + sums[i-1][j] - sums[i-1][j-1] + map[i][j];
			}
		}
		
		 StringBuilder sb = new StringBuilder();
		// 사각형 누적합 계산
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x1 =  Integer.parseInt(st.nextToken()); //x1
			int y1 =  Integer.parseInt(st.nextToken()); //y1
			int x2 =  Integer.parseInt(st.nextToken()); //x2
			int y2 =  Integer.parseInt(st.nextToken()); //y2
			
			sum = sums[x2][y2] - sums[x1-1][y2] - sums[x2][y1-1] + sums[x1-1][y1-1];
			sb.append(sum).append('\n');
		}	
		System.out.println(sb);;
	}
}

혹시 잘못된 정보나 궁금하신 내용이 있으시면 댓글로 남겨주시면 감사드리겠습니다.