백준[node.js] > 11660번 구간 합 구하기5

 

문제링크

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

 

문제풀이

이 문제는 언뜻보면 쉬어보인다. 하지만 단순하게 풀면 연산횟수가 너무 많아 시간초과가 난다. 

연산횟수를 확인히 줄이기 위해 dp(동적계획법-dynamic programming)를 이용해야 한다. 

dp를 생각하는 순간 문제는 쉬어진다.

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

let [tableInfo, ...arr] = input;

let [N, M] = tableInfo.split(" ").map((num) => Number(num));

let table = [];
for (let i = 0; i < N; ++i) {
    table.push(arr[i].split(" ").map((num) => Number(num)));
}

let dp = Array.from({ length: N }, () => {
    return Array(N).fill(0);
});

for (let row = 0; row < N; ++row) {
    for (let col = 0; col < N; ++col) {
        if (row === 0 && col === 0) {
            dp[0][0] = table[0][0];
            continue;
        }

        if (col === 0) {
            dp[row][col] = dp[row - 1][col] + table[row][col];
            continue;
        }

        if (row === 0) {
            dp[row][col] = dp[row][col - 1] + table[row][col];
            continue;
        }

        dp[row][col] = dp[row - 1][col] + dp[row][col - 1] - dp[row - 1][col - 1] + table[row][col];
    }
}

for (let i = N; i < arr.length; ++i) {
    let [r1, c1, r2, c2] = arr[i].split(" ").map((num) => Number(num));

    let sum = dp[r2 - 1][c2 - 1];

    if (r1 - 2 >= 0) {
        sum -= dp[r1 - 2][c2 - 1];
    }

    if (c1 - 2 >= 0) {
        sum -= dp[r2 - 1][c1 - 2];
    }

    if (r1 - 2 >= 0 && c1 - 2 >= 0) {
        sum += dp[r1 - 2][c1 - 2];
    }

    console.log(sum);
}