[boj] 11660. 구간 합 구하기 5 (node.js)

문제

[boj] 11660. 구간 합 구하기 5 (node.js)

풀이

• 문제를 이해하는 것은 간단하나, 직관적으로 떠올릴 수 있는 답인 이중 반복문을 사용해 풀이하는 경우 시간 초과가 발생하는 문제다.
• 구간의 누적합을 구할 때 동적 프로그래밍 기법을 사용해 문제를 풀이하는 것이 시간 복잡도를 크게 낮출 수 있다는 사실을 인식하고 이 방법으로 접근해야 한다.

핵심 풀이

• 먼저 dp 배열을 정의(초기화)한다.
  • dp[i][j] = 1행 1열부터 i행 j열까지의 값의 누적합
  • dp 계산을 위해 입력과 동시에 dp 배열을 누적값으로 초기화한다.

for (let j = 0; j < N; j++) {
  dp[i][j] = arr[i][j];
  if (i !== 0) dp[i][j] += dp[i - 1][j];
  if (j !== 0) dp[i][j] += dp[i][j - 1];
  if (i == 0 || j == 0) continue;
  dp[i][j] -= dp[i - 1][j - 1];
}

• dp 배열에 저장해둔 값을 활용하여 문제에서 구하고자 하는 값을 계산하는 함수를 정의했다.
• 문제에서는 (r1, c1) ~ (r2, c2) 구간의 누적합을 계산하고자 한다.
  • dp 값에 해당 구간까지의 누적합을 저장해둔 상태이므로, 이 값을 활용해 특정 구간의 합을 구하는 식을 세우면 아래와 같다.
  • (r1, c1) ~ (r2, c2) 구간의 누적합 = dp[r2][c2] - dp[r1 - 1][c2] - dp[r2][c1 - 1] + dp[r1 - 1][c1 - 1]

function sum(r1, c1, r2, c2) {
  let result = dp[r2][c2];
  if (r1 !== 0) result -= dp[r1 - 1][c2];
  if (c1 !== 0) result -= dp[r2][c1 - 1];
  if (r1 === 0 || c1 === 0) return result;
  return result + dp[r1 - 1][c1 - 1];
}

생각

• 얼마 전 풀이해본 프로그래머스 스킬체크 레벨 2에서 이 유형의 문제들을 처음 접했는데, 풀이 시간제한 때문에 풀이를 하지 못했었다. DP가 아닌 반복문 형식으로 함수를 정의해 풀이했었는데, 오늘 랜덤하게 고른 이 문제 덕에 DP 유형이라는 걸 알 수 있었다. 우연찮게 한 발 나아갈 실마리를 얻어 기쁘다. 😁

전체 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = () => {
  const arr = [];
  const dp = [];
  const [N, M] = input().split(" ").map(Number);
  for (let i = 0; i < N; i++) {
    arr[i] = input().split(" ").map(Number);
    dp[i] = [];
    for (let j = 0; j < N; j++) {
      dp[i][j] = arr[i][j];
      if (i !== 0) dp[i][j] += dp[i - 1][j];
      if (j !== 0) dp[i][j] += dp[i][j - 1];
      if (i == 0 || j == 0) continue;
      dp[i][j] -= dp[i - 1][j - 1];
    }
  }

  const results = [];
  for (let i = 0; i < M; i++) {
    const [x1, y1, x2, y2] = input().split(" ").map(Number);
    results.push(sum(x1 - 1, y1 - 1, x2 - 1, y2 - 1));
  }
  console.log(results.join("\n"));

  function sum(r1, c1, r2, c2) {
    let result = dp[r2][c2];
    if (r1 !== 0) result -= dp[r1 - 1][c2];
    if (c1 !== 0) result -= dp[r2][c1 - 1];
    if (r1 === 0 || c1 === 0) return result;
    return result + dp[r1 - 1][c1 - 1];
  }
};

let line = 0;
const input = () => stdin[line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});