[BOJ 11660] 구간 합 구하기 5

문제

구간 합 구하기 5

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

 

 

풀이

설명

(x1, y1)부터 (x2, y2)까지 합을 구하는 구하는 문제입니다.

 

DP를 이용해 해결할 수 있습니다.

 

dp[i][j]는 (1, 1)부터 (i, j)까지의 합입니다.

 

점화식은 다음과 같습니다.

dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]

 

예시 코드

function solution() {
  const [N, M] = input().split(" ").map(Number);
  const board = Array.from({ length: N }, () => input().split(" ").map(Number));
  const dp = Array.from({ length: N + 1 }, () => Array(N + 1).fill(0));
  const answer = [];

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

  for (let i = 0; i < M; i++) {
    const [x1, y1, x2, y2] = input().split(" ").map(Number);
    answer.push(
      dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]
    );
  }

  return answer.join("\n");
}