[백준11660_자바스크립트(javascript)] - 구간 합 구하기 5

🔴 문제

구간 합 구하기 5

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));
const [n, m] = inputs[0];
const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
const map = [];

for (let i = 1; i <= n; i++) {
  map.push(inputs[i]);
}

for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n; j++) {
    dp[i][j] = map[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
  }
}

for (let i = n + 1; i <= n + m; i++) {
  const [x1, y1, x2, y2] = inputs[i];
  const ans = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
  console.log(ans);
}

🟢 풀이

⏰ 소요한 시간 : -

dp와 누적합을 사용해 풀이했다.

문제에서 요구하는 영역은 파란색으로 둘러싸인 영역에서, 주황색으로 둘러쌓인 두 개의 영역을 빼주면 된다. 다만 두 영역을 빼줄때 연두색으로 둘러싸인 영역이 중복으로 제거되므로 이 영역을 다시 구해주면 된다.
즉 아래와 같은 공식이 나온다.

요구하는 영역 = 파란색영역 - 주황색영역1 - 주황색영역2 + 연두색영역

이런 영역을 구하기 위해서 각 영역의 크기를 관리하는 dp 배열을 만들었다
dp 배열은 아래와 같이 정의했다.

// (1,1) 좌표부터 (i,j) 좌표까지의 누적합

dp[i][j] = map[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];

dp 좌표를 모두 채워준 뒤, 위에서 정의했던 공식대로 요구하는 영역의 누적합을 구해주면 된다.

🔵 Ref