Life Study

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

이 문제를 보기 전까지는 구간합도 할 만하다고 생각하다가 딱 이 문제를 보는 순간,
와.. 내가 이걸 풀 수 있을까 이 생각이 들었다. 나한테는 이 문제가 거의 최종 보스처럼 느껴졌다.
왜냐하면 필자는 2차원 배열에 울렁증이 있기 때문이다. 전 직장에서도 배열을 다루는 게 능숙지 않아 보인다는 말을 여러 번 들었을 정도로 초보중의 초보였다. 그런데 이런 문제를 분석해서 푼다? 정말 가능성이 단 1도 없어 보였다.
하지만 이 역시 분석하지 않고 넘어가게 되면 결국엔 다른 직장에 가서도 똑같은 소리를 듣게 될 게 뻔하고,
결국 공부다운 공부를 못한 것이 되어버린다. 그래서 이 문제도 하나하나 분석을 해나갔다.
결과적으로는 분석을 해냈고, 2차원 배열의 거부감도 조금은 덜게 되었다.

서론이 좀 길었는데, 먼저 2차원 배열에 대해서 알아보자.
2차원 배열이란, 말 그대로 1차원 배열이 여러 개로 이루어져 있어, 면 형태를 띠고 있다고 보면 된다.

따라서 이 2차원 배열을 다루기 위해선 2중 반복문이 거의 필수적으로 나온다.
책에서는 구간합 알고리즘을 기준으로 알려주기 때문에,
구간합 알고리즘을 이용한 문제풀이 방식을 분석한 것이다.
필자가 구글링으로 알아본 결과, 이 문제에서는 DP(Dynamic Programing)보다 구간합 알고리즘이 속도가 빠르다고 하여 구간합에 집중할 수 있었다. DP에 대해서는 아직 공부를 못했기 때문에, 차후에 글을 작성해볼 생각이다.

생각하기 쉽게 예제를 통해 생각을 해보자.
처음에 4를 입력해서 4칸x4칸 = 16칸의 2차원 배열이 만들어졌다.
그러면서 값을 순서대로 넣기 시작한다. 그럼 이렇게 그림이 그려진다.

우린 여기서 구간합을 구해야 하기 때문에 결국 누적합을 구해야 한다.
근데 어떻게 구해야 위, 아래로 더해지는 것도 대비를 할 수 있을까?

책에서 나온 공식이 있지만, 역시나 필자는 한 번에 이해를 하지 못했기 때문에 하나씩 분석을 해봤다.
누적 합의 배열도 역시나 2차원 배열일 수밖에 없다. 왜냐하면 숫자를 입력받은 배열 자체가 2차원이기 때문이다.

일단 일차원 누적합은 간단했다. S[i] = S[i-1] + N[i]. 근데, 이 문제는 좀 더 복잡하다.
우리가 만들 누적 합의 값을 적어보자면 위와 같은 식이다. 따라서 우리는 N[i][j]도 더해줘야 하는 것이다.
이유는 https://life-study-1031.tistory.com/7 여기에서 잘 설명되어있으니 참고 바란다.

돌아와서, 일차원의 누적합을 저장할 때는 S[i] = S[i-1] + N[i] 이 형태로 했었는데,
이건 2차원 배열임을 다시 한번 상기시키면서 생각해보자,
S[i-1]을 더하는 이유는 결국 그 항이 이번 항 그 전까지의 누적합이기 때문에 더하는 것이다.
그럼 2차원에서는 어떻게 해야 그 전항까지의 값을 더할 수 있을까?
바로 가로줄과 세로줄을 하나씩 줄인 값을 더하는 것이다.

여기서 우리가 알아야 할 것은, 이차원 배열을 다룰 때 A[i][j] 이런 형태로 다루게 되는데,
이 원리를 잘 알아야 한다는 것이다. 단도직입적으로 말하면 A[(가로줄)][(세로줄)]이다.
이걸 그림으로 설명해보자면 아래와 같다.

그렇게 되면 만약에 S(i,j) = S(2,3)의 누적합을 구해야 한다고 했을 때, S(1,3)은 결국 N(1,1)~N(1,3)까지 더한 값이며, S(2,2)는 N(1,1)+N(1,2)+N(2,1)+N(2,2)를 다 더한 값이기 때문에 1차원 배열에서 했던 현재항 이전의 항을 더하는 것과 동일한 수순이 되는 것이다.

그런데 이렇게 한 줄씩 줄인 것을 더하게 되면 문제가 생긴다. 그럼 2번 더해지는 부분이 생길 텐데, 그 부분은 빼줘야 하지 않은가? 그래서 현재 항의 대각선에 있는 항은 빼준다. 예를 들어 S(2,3)을 구한다고 해보면, N(1,1), N(1,2)는 중복으로 더해진다. 따라서 이런 부분을 빼주기 위해 대각선에 있는 항을 빼주는 것이다.

그럼 이제 남은 건 하나다.
예제에서 나오는 S(2,2) ~ S(3,4)까지의 합을 어떻게 구할 것이냐?

이것도 그림으로 보면 편하다.

갈색으로 칠한 부분이 N(1,1) ~ N(3,4)까지 모두 더한 값이고, 분홍색은 거기에서 N(1,1) ~ N(1,4)까지 더한 값이다.
그리고 보라색은 N(1,1) ~ N(3,1)까지 더한 값이다.
즉, 우리는 저 값들을 빼야 N(2,2) ~ N(3,4)까지의 값을 더할 수 있다.
다만 그러면 두 번 빼게 되는 값이 있다. 바로 N(1,1), N(1,2)이다. 따라서 처음에 입력받는 x,y 값에서 1씩 빼주면 두 번 빼게 되는 값을 가리킬 수 있고, 그걸 더해주면 되는 것이다.

여기까지 오느라 정말 머리가 터질 것 같은 기분 너무 잘 안다. 이제 진짜 다 왔다.
우리는 이걸로 2가지를 도출할 수 있다.
① 2차원 배열에서 구간합을 구하는 식:
     S[(가로줄)][(세로줄)] = S[(가로줄)-1][(세로줄)] + S[(가로줄)][(세로줄)-1] - S[(가로줄)-1][(세로줄)-1]
② 질의에 대한 답을 구할 수 있는 식(x1, y1은 처음에 입력받는 좌표, x2, y2는 두 번째로 입력받는 좌표): 
     S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]

이걸 코딩으로 표현하자면 아래와 같다.

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

public class BOJ_11660 {

	public static void main(String[] args) throws IOException{
		// TODO 백준 11660
		
        //입력을 빨리 받기 위해 BufferedReader 클래스를 사용함.
        //입력받은 문자열을 파싱하기 위해 StringTokenizer 클래스를 사용함.
		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[][] nums = new int[N+1][N+1];
		long[][] sums = new long[N+1][N+1];

		//숫자 입력받고 합 구하기
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=N; j++) {
				nums[i][j] = Integer.parseInt(st.nextToken());
				sums[i][j] += sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + nums[i][j];
			}
		}
		
		//답 구하기
		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());
			
			System.out.println(sums[x2][y2] - sums[x1-1][y2] - sums[x2][y1-1] + sums[x1-1][y1-1]);
		}
	}
}