구간 합 구하기 5

문제

언어

  • JavaScript

순서도

  1. 점화식을 정의하고, 그에 맞게 dp 배열 생성하기
  2. dp 배열의 base 값 정의
  3. 점화식과 base 값을 이용해서 dp 배열 채우기
  4. 각 테스트케이스마다 dp 배열을 이용해서 값 생성하기

문제 풀이 step 1

  • N x N 크기의 표의 각 칸에 수가 채워져 있습니다. 이 때, (x1, y1) 부터 (x2, y2) 까지 합을 구하는 문제입니다.
  • DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
  • dp[x][y] = (0, 0) 부터 (x, y) 까지의 합
  • 점화식은 dp[x][y] = dp[x - 1][y] + dp[x][y - 1] - dp[x - 1][y - 1] + table[x][y] 입니다.
    • 점화식을 풀어서 설명하면,
    • (0, 0) 부터 (x - 1, y) 까지의 합과 (0, 0) 부터 (x, y - 1) 까지의 합을 더하고,
    • 중복해서 더해진 부부인 (0, 0) 부터 (x - 1, y - 1) 까지의 합을 빼주고,
    • (x, y) 칸의 값을 더하는 것입니다.
  • base 는 dp[0][0] 으로 값은 table[0][0] 입니다.
    • 그리고 0 행의 모든 칸(dp[0][0, 1, …, n])을 누적합을 통해서 다 채우고,
    • 0 열의 모든 칸(dp[0, 1, …, n][0])을 누적합을 통해서 다 채우면 됩니다.
  • 그리고 점화식과 base 값을 이용해서 dp 배열을 모두 채웁니다.

문제 풀이 step 2

  • 채운 dp 배열을 이용해서 각 테스트케이스마다 구간 합을 구해야 합니다.
  • 이는 점화식과 비슷한 연산을 통해서 가능합니다.
  • 예를 들어, (1, 2) 부터 (4, 3) 까지의 합을 구할 때, dp[4][3] - dp[0][2] - dp[1][1] + dp[0][1] 을 구하면 됩니다.
    • 위의 식을 풀어서 설명하면,
    • (0, 0) 부터 (4, 3) 까지의 합에서
    • (0, 0) 부터 (0, 2) 까지의 합과 (0, 0) 부터 (1, 1) 까지의 합을 빼주고,
    • 중복해서 빼진 부분인 (0, 0) 부터 (0, 1) 까지의 합을 더하는 것입니다.
  • 각 테스트케이스마다 위의 식을 적용해서 구간 합을 구하고 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);
	const table = input.slice(1, n + 1).map((v) => v.split(" ").map(Number));

	const dp = Array.from({length: n}, () => Array(n).fill(0));

	// base
	dp[0][0] = table[0][0];
	// base - 0 행 채우기
	for (let j = 1; j < n; j++) {
		dp[0][j] = dp[0][j - 1] + table[0][j];
	}
	// base - 0 열 채우기
	for (let i = 1; i < n; i++) {
		dp[i][0] = dp[i - 1][0] + table[i][0];
	}

	// 점화식을 이용해서 dp 배열 채우기
	for (let i = 1; i < n; i++) {
		for (let j = 1; j < n; j++) {
			dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + table[i][j];
		}
	}

	// 각 테스트케이스마다 구간 합 구하기
	let res = "";
	for (let i = n + 1; i < n + 1 + m; i++) {
		let [x1, y1, x2, y2] = input[i].split(" ").map(Number);
		[x1, y1, x2, y2] = [x1 - 1, y1 - 1, x2 - 1, y2 - 1];

		let num = dp[x2][y2];

		if (x1 === 0 && y1 !== 0) {
			num -= dp[x2][y1 - 1];
		}

		if (x1 !== 0 && y1 === 0) {
			num -= dp[x1 - 1][y2];
		}

		if (x1 !== 0 && y1 !== 0) {
			num -= dp[x1 - 1][y2] + dp[x2][y1 - 1] - dp[x1 - 1][y1 - 1];
		}

		res += num + "\n";
	}

	return res;
};

console.log(solution(input));