BOJ_2167 2차원 배열의 합

• TOC {:toc}

이 글은 백준 온라인 저지의 2167번 문제를 자바스크립트(JavaScript)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2023.02.24

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

const [NM, ...lines] = input;
const [N, M] = NM.split(" ").map((n) => parseInt(n));
const matrix = lines.slice(0, N).map((line) => line.split(" ").map((n) => parseInt(n)));

function main() {
    for (let i = 0; i < N; i += 1) {
        for (let j = 0; j < M; j += 1) {
            matrix[i][j] += (i && matrix[i - 1][j]) + (j && matrix[i][j - 1] - (i && j && matrix[i - 1][j - 1]));
        }
    }

    for (let k = 0; k < lines[N]; k += 1) {
        const [i, j, x, y] = lines[N + k + 1].split(" ").map((n) => parseInt(n));
        console.log(
            matrix[x - 1][y - 1] -
                (i - 1 && matrix[i - 2][y - 1]) -
                (j - 1 && matrix[x - 1][j - 2]) +
                (i - 1 && j - 1 && matrix[i - 2][j - 2])
        );
    }
}

main();

아이디어 & 풀이

기존 행렬에서 매번 주어진 좌표와 좌표사이을 더해서 값을 구하는 것보다, (1, 1)을 기준으로 해당 지점까지의 합을 구해놓은 새로운 행렬을 만들어 (i, j)와 (x, y)의 값을 연산해서 구하는 게 계산이 더 효율적이다.

우선 (1, 1)을 기준으로 해당 지점까지의 합을 구해놓은 새로운 행렬을 구한다.

• 1, 1에서 출발해서 i와 j을 증가시키면서 인접한 이전값을 이용해 값을 계산할 수 있다.

• (i, j)의 값은 (i - 1, j)의 값과 (i, j - 1)의 값을 더한 뒤 중복인 (i - 1, j - 1)의 값을 빼주면 된다.

• 예를 들어 (3, 4)의 경우 각 영역을 나타내면 다음과 같다.

  (3, 4)    | (2, 4)    | (3, 3)    | (2, 3)   
  X X X X O | X X X X O | X X X O O | X X X O O
  X X X X O | X X X X O | X X X O O | X X X O O
  X X X X O | O O O O O | X X X O O | O O O O O
  O O O O O | O O O O O | O O O O O | O O O O O
  

  • i - 1, j - 1이 영역 밖으로 나갈 수 있으므로 각 값이 쓰이는 곳 앞에 [i or j] && 조건을 붙여서 i나 j의 값이 false(0)일 경우 더하거나 빼는 값으로 0을 반환할 수 있도록 한다.

(i, j)부터 (x, y) 까지의 합을 구하는 원리는 위와 유사하다. (2, 3)에서 (4, 5) 까지의 합을 구한다고 할 때

• 구하는 영역은 다음과 같다.

  O O O O O
  O O X X X
  O O X X X
  O O X X X
  

• 이는 (4, 5)의 영역에서 다음의 영역을 빼고 중복되는 부분을 더한 값과 같다.

  • 빼는 영역

  (1, 5)    | (4, 2)    
  X X X X X | X X O O O
  O O O O O | X X O O O
  O O O O O | X X O O O
  O O O O O | X X O O O
  

  • 중복 영역

  (1, 2)    
  X X O O O 
  O O O O O 
  O O O O O 
  O O O O O 
  

• 이를 일반화 하면 다음과 같으므로

  • 빼는 영역 1: (i - 1, y)
  • 빼는 영역 2: (x, j - 1)
  • 중복 영역: (i - 1, j - 1)

• 값을 구하는 수식은 다음과 같다.

  matrix[x - 1][y - 1] -
      (i - 1 && matrix[i - 2][y - 1]) -
      (j - 1 && matrix[x - 1][j - 2]) +
      (i - 1 && j - 1 && matrix[i - 2][j - 2])
  

  • 역시 행렬이 범위 밖으로 벗어나는 것을 방지하기 위해서 앞에 위와 같이 조건 처리를 해주었다.

피드백

• dp 문제라서 dp로 풀었는데 시간이 너무 오래걸린 거 보니 그냥 i ~ x , j ~ y 순회해서 푸는 것 같다.
  • 해봤는데 dp가 훨씬 빠르다. 다른 사람들과 시간 차이가 나는 것은 다른 이유일듯.
• K의 값이 꽤 커서 모든 결과를 각 줄로 출력하는 것보다 res에 넣은 다음에 join으로 각 줄로 결합헤서 한 번 출력하는 게 훨씬 빠르다.
• 가로 세로 합을 어렵게 계산할 것 없이 한 방항을 먼저 더하고, 다음으로 다른 방향을 더해도 된다.

참고 답안

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

const [NM, ...lines] = input;
const [N, M] = NM.split(" ").map((n) => parseInt(n));
const matrix = lines.slice(0, N).map((line) => line.split(" ").map((n) => parseInt(n)));

function main() {
    res = [];
    for (let i = 0; i < N; i += 1) {
        for (let j = 1; j < M; j += 1) {
            matrix[i][j] += matrix[i][j - 1];
        }
    }
    for (let i = 1; i < N; i += 1) {
        for (let j = 2; j < M; j += 1) {
            matrix[i][j] += matrix[i - 1][j];
        }
    }

    for (let k = 0; k < lines[N]; k += 1) {
        const [i, j, x, y] = lines[N + k + 1].split(" ").map((n) => parseInt(n));
        res.push(
            matrix[x - 1][y - 1] -
                (i - 1 && matrix[i - 2][y - 1]) -
                (j - 1 && matrix[x - 1][j - 2]) +
                (i - 1 && j - 1 && matrix[i - 2][j - 2])
        );
    }
    return res.join("\n");
}

console.log(main());

아이디어 & 풀이

• 위의 피드백을 모두 반영한 풀이.