15724번 - 주지수

1️⃣ 부분합

 

✏️ 풀이 과정

N, M이 최대 1024, 즉 격자의 수가 대략 100만개이고 범위의 개수도 10만개이기 때문에 반드시 부분합을 이용해서 O(N)에 해결해야 합니다. 1차원이 아닌 2차원 부분합을 적용해야 하는데 방법은 아래 그림과 같습니다. 부분합의 각 좌표는 1,1부터 x,y까지의 합을 의미합니다.

일반화하면 (x2, y2)에서 (x1-1, y2)와 (x2, y1-1)을 빼고 두 번 감산된 (x1-1, y1-1)을 한 번 더해줌으로써 항상 원하는 영역의 합을 얻을 수 있습니다.

 

위의 부분합 이차원 배열을 만드는 방법은 각자 다를 수 있지만 아래 코드에서는 열 방향으로 일차원 부분합을 우선 구하고 바로 윗 행의 부분합 결과를 더해주는 방법으로 만들었습니다.

 

⏱ 시간 복잡도

계산 자체는 참조 4번으로 끝나기 때문에 부분합을 만드는 O(N * M)이 전체 시간복잡도가 됩니다. 만약 K가 N*M보다 커질 수 있는 경우에는 K도 고려하여 O(N * M + K)로 표현할 수 있습니다. 문제의 조건에서는 대략 백만 단위의 계산으로 해결되는 것을 예측할 수 있습니다. 

 

💻 코드

Java

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());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] pSum = 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++) {
        		pSum[i][j] = pSum[i][j-1] + Integer.parseInt(st.nextToken());
        	}
        	for(int j=1;j<=M;j++) {
        		pSum[i][j] += pSum[i-1][j];
        	}
        }
        int K = Integer.parseInt(br.readLine());
        int x1, y1, x2, y2;
        for(int i=0;i<K;i++) {
        	st = new StringTokenizer(br.readLine());
        	x1 = Integer.parseInt(st.nextToken());
        	y1 = Integer.parseInt(st.nextToken());
        	x2 = Integer.parseInt(st.nextToken());
        	y2 = Integer.parseInt(st.nextToken());
        	sb.append(pSum[x2][y2] - pSum[x2][y1-1] - pSum[x1-1][y2] + pSum[x1-1][y1-1] +"\n");
        }
        System.out.print(sb);
        br.close();
    }
}

JavaScript

const input = require("fs")
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
    .toString()
    .trim()
    .split("\n");

const [N, M] = input[0].split(" ").map(Number);
const pSum = Array.from(Array(N + 1), () => Array(M + 1).fill(0));
for (let i = 1; i <= N; i++) {
    input[i].split(" ").map((item, j) => {
        pSum[i][j + 1] = pSum[i][j] + Number(item);
    });
    pSum[i].map((_, j) => {
        pSum[i][j + 1] += pSum[i - 1][j + 1];
    });
}

const K = Number(input[N + 1]);
const ans = [];
for (let i = N + 2; i < N + 2 + K; i++) {
    const [x1, y1, x2, y2] = input[i].split(" ").map(Number);
    ans.push(
        pSum[x2][y2] -
            pSum[x1 - 1][y2] -
            pSum[x2][y1 - 1] +
            pSum[x1 - 1][y1 - 1]
    );
}
console.log(ans.join("\n"));