[백준 11660 - Node.js] 구간 합 구하기 5

🔗 문제 링크

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

11660번: 구간 합 구하기 5

✏️ 풀이

const [[N, M], ...input] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map(v => v.split(' ').map(Number));

const table = Array.from({ length: N + 1 }, () => Array(N + 1).fill(0));

input.slice(0, N).forEach((row, x) => {
  row.forEach((cell, y) => {
    table[x + 1][y + 1] = cell;
  });
});

for (let x = 1; x <= N; x++) {
  for (let y = 1; y <= N; y++) {
    table[x][y] += table[x - 1][y] + table[x][y - 1] - table[x - 1][y - 1];
  }
}

const coords = input.slice(N);
const output = [];

coords.forEach(([x1, y1, x2, y2]) => {
  output.push(table[x2][y2] - table[x1 - 1][y2] - table[x2][y1 - 1] + table[x1 - 1][y1 - 1]);
});

console.log(output.join('\n'));

이 문제는 주어진 표의 크기가 크기 때문에 매번 좌표가 주어질 때마다 값을 계산하면 시간 초과가 난다. 따라서 DP를 활용해서 시간복잡도를 줄여야 한다.

 

먼저 각 구간의 합을 미리 구해 놓는다. 구간합은 각 칸에 (1, 1)부터 (x, y)까지의 합을 저장함으로써 구현할 수 있다. 이 때 매번 (1, 1)부터 (x, y)까지의 합을 구하지 않고 앞에서부터 순차적으로 구해놓은 값을 활용해서 구간합을 구할 수 있다.

 

예를 들어 (3, 3)의 구간합은 (원래 표의 (3, 3)에 위치한 값) + (2, 3) 구간합 + (3, 2) 구간합 - (2, 2) 구간합으로 구할 수 있다. (1, 1)부터 차례대로 순회하면서 구간합을 구한다면 바로 위 칸, 왼쪽 칸, 대각선 왼쪽 위 칸의 값을 활용할 수 있다. 단, 첫 번째 행이나 열에서는 위 칸, 왼쪽 칸, 대각선 왼쪽 위 칸이 존재하지 않을 수도 있으므로, 처음부터 구간합 테이블을 (N + 1)의 크기로 만들어서 남는 공간은 0으로 초기화해두면 된다. 이렇게 하면 (1, 3)의 구간합을 구할 때 (0, 3), (0, 2)에 초기화된 0을 사용하여 오류가 나지 않는다.

 

주어진 좌표들을 순회하면서 구간합 표를 활용하여 해당 (x1, y1)부터 (x2, y2)까지의 합을 구하면 된다. 이 때 이 구간합은 (x2, y2) 구간합 - (x1 - 1, y2) 구간합 - (x2, y1 - 1) 구간합 + (x1 - 1, y1 - 1) 구간합으로 구할 수 있다.

 

예를 들어 (2, 2) ~ (3, 3)의 구간합은 (1, 1) ~ (3, 3)의 구간합에서 (1, 1) ~ (1, 3)의 구간합과 (1, 1) ~ (3, 1)의 구간합을 빼고 중복으로 뺀 (1, 1) ~ (1, 1) 구간합을 다시 더한 것과 같다. 따라서 구간합 테이블의 (3, 3) - (1, 3) - (3, 1) + (1, 1)을 통해 (2, 2) ~ (3, 3)의 구간합을 구할 수 있다.

 

 

참고자료

https://chanhuiseok.github.io/posts/baek-19/

[백준] 11660번 - 구간 합 구하기 5