[백준 Java] 15724번 주지수( DP, 2차원 배열 누적합)

 

[Silver I] 주지수 - 15724

문제 링크

성능 요약

메모리: 121296 KB, 시간: 648 ms

분류

다이나믹 프로그래밍, 누적 합

문제 설명

네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 주지수를 만들기 위해서 일정한 직사각형 범위 내에 살고 있는 사람 수를 참고 자료로 쓰고 싶어한다.

진경대왕은 굉장히 근엄한 왕이기 때문에 당신에게 4개의 숫자로 직사각형 범위를 알려줄 것이다.

예를 들어, 위와 같이 사람이 살고 있다고 가정할 때 <그림 1>의 직사각형 범위의 사람 수를 알고 싶다면 진경대왕은 네 개의 정수 1 1 3 2를 부를 것이다. 마찬가지로 <그림 2>는 1 1 1 4, <그림 3>은 1 1 4 4가 될 것이다.

진경대왕을 위하여 이 참고 자료를 만들어내는 프로그램을 작성해보자.

입력

첫째 줄에 영토의 크기 N, M(1 ≤ N, M ≤ 1,024)이 주어진다.

다음 N개의 줄에는 M개의 정수로 단위 구역 내에 살고 있는 사람 수가 주어진다. 각 단위 구역 내에 살고 있는 사람 수는 100명 이하이며, 각 단위 구역 별 최소 1명의 사람은 살고 있다.

그 다음 줄에는 진경대왕이 인구 수를 궁금해하는 직사각형 범위의 개수 K(1 ≤ K ≤ 100,000)가 주어진다.

다음 K개의 줄에는 네 개의 정수로 직사각형 범위 x1, y1, x2, y2가 주어진다(x1 ≤ x2, y1 ≤ y2).

출력

K개의 줄에 순서대로 주어진 직사각형 범위 내에 살고 있는 사람 수의 합을 출력한다.

💡 나의 접근

처음에는 x1, y1을 시작으로 x2 만큼 증가, y2만큼 증가하여 구간내 합을 구하는 것인 줄 알았으나...

x1, y1 부터 x2, y2 까지의 구간 내 합을 구하는 것이었다.

(x1 ≤ x2, y1 ≤ y2). 라는 조건에서 힌트를 얻었어야 했는데 나중가서 다른 사람이 푼 풀이를 보고 알아냈다.

 

또 처음에는 누적합이라는 것을 생각해내지 못했다.

합을 구하는 문제이고 배열의 시작이 1로 시작한다면 누적합을 의심해보자

 

위 그림을 식으로 나타내면

peopleDP[i][j] = peopleDP[i-1][j] + peopleDP[i][j-1] - peopleDP[i-1][j-1] + peopleDP[i][j];

이다.

이렇게 누적합 배열이 만들어지면 구간내 누적 합을 구해야하는데 

아래 그림은 누적합 배열이 아닌 주어진 배열에서 구간 내 합을 구하는 방법이다.

이를 누적합 배열에서 구하면 아래와 같다.

이를 식으로 나타내면

sum = peopleDP[x2][y2] - peopleDP[x1-1][y2] - peopleDP[x2][y1-1] + peopleDP[x1-1][y1-1]

와 같다.

 

 

💡 코드

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


public class Main {
	//합을 구하는 문제이고 배열의 시작이 1로 시작한다면 누적합을 의심해보자
	static int N;
	static int M;
	static int peopleDP[][];
	static int K;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		peopleDP = new int [N+1][M+1];
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= M; j++) {
				int value = Integer.parseInt(st.nextToken());
				peopleDP[i][j]= value + peopleDP[i-1][j]+peopleDP[i][j-1] - peopleDP[i-1][j-1];
			}
		}
		
		//-----입력을 받으면서 누적합으로 바꿈
		
		
		K = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		
		for (int k = 0; k < K; k++) {
			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());
			for (String string : args) {
				
			}
	
			sb.append(peopleDP[x2][y2] - peopleDP[x1-1][y2] - peopleDP[x2][y1-1]+peopleDP[x1-1][y1-1]).append("\n");
		}
		System.out.println(sb.toString());
	}

}