[백준 | Java] 11660번: 구간 합 구하기 5

백준 11660번: 구간 합 구하기 5 문제 링크

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 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)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

---

소스코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
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[][] map = 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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int[][] sum = new int[n+1][n+1]; // 누적합 배열
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                sum[i][j] = map[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
            }
        }

        ArrayList<Point[]> list = new ArrayList<>();
        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());
            list.add(new Point[]{new Point(x1, y1), new Point(x2, y2)});
        }
        int answer = 0;
        for(int i=0; i<list.size(); i++) {
            int r2 = list.get(i)[1].x;
            int c2 = list.get(i)[1].y;
            int r1 = list.get(i)[0].x;
            int c1 = list.get(i)[0].y;
            answer = sum[r2][c2] - (sum[r2][c1-1] + sum[r1-1][c2]) + sum[r1-1][c1-1];
            System.out.println(answer);
        }

    }
}

풀이

먼저 코드를 어떻게 써야할 지 생각해봤다.

1. 좌표는 일단 포인트 배열로 받자
2. 이중반복문으로 풀다간 시간초과 백퍼날 것 같다
3. -> 누적 합 배열로 풀자

누적 합 배열 만들기

• 1행의 누적 합은 1, 3, 6, 10이 나오는데 이걸 공식으로 만들면

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

• 1열의 누적 합 또한 1, 3, 6, 10이 나오는데 얘도 공식으로 만들면

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

이렇게 나온다.

그럼 (2,2)의 누적 합 값인 8은 그럼 어떻게 나왔을까?

사진에서 보다시피 (1,2)의 누적 합 + (2,1)의 누적 합에 중복으로 더해진 (1,1)의 값을 뺀 다음 원본 숫자 배열 좌표값인 (2,2)의 값을 더하면 나온다.

-1행한 누적값 + -1열한 누적값 - 중복으로 더해진 왼쪽 위의 대각선에 위치한 누적값 + 원 좌표값

이걸 공식으로 나타내면

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

위의 공식을 적용한 예제의 누적 합 배열은 이렇게 나온다.

누적 합 배열을 바탕으로 구간 합 계산하기

예제의 구간 합은 (2,2) ~ (3,4)까지의 합을 구하는 것이었다.

일단 (3,4)까지의 누적 합 값인 42에서 (3,1)의 누적 합 값과 (1,4)의 누적 합 값을 빼주고 중복으로 빼준 (1,1)의 누적 합 값을 더해주면 42 - ( 6 + 10 ) + 1 => 27 의 값이 나온다.

임의의 테스트케이스를 만들어 다시 확인해보자. 이번엔 (2, 3) ~ (4, 4)의 구간 합을 구한다고 가정했을 때

이런 형태로 (4, 4)까지의 누적 합 값에서 (4,2)의 누적합 값과 (1, 4)의 누적 합 값을 빼주고 중복으로 빼준 (1,2)의 누적 합 값을 더해주면 64 - ( 24 + 10 ) + 3 => 33 이 나온다.

이제 이걸 공식으로 만들면 이렇게 나온다.

sum[r2][c2] - (sum[r2][c1-1] + sum[r1-1][c2]) + sum[r1-1][c1-1];

---

나중에 dp로 한 번 더 풀어봐야겠다!