[JavaScript] 백준 11660 : 구간 합 구하기 5

class : 4

level : silver 2

문제 링크 : 구간 합 구하기 5

11660번: 구간 합 구하기 5

My Solution

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();
input = input.split('\n');
const [N, M] = input.shift().split(' ').map(Number);
let matrix = input.slice(0,N).map(str=>str.split(' ').map(Number));
input = input.splice(N).map(str=>str.split(' ').map(Number));
let answer = '';
let dp = new Array(N);
/// 2d array deep copy
matrix.forEach((val,ind)=>{
    dp[ind] = val.slice(0);
});
matrix.forEach((arr,index) => {
    arr.forEach((item, i)=>{
        dp[index][i] = item ;
        if(i!==0) dp[index][i] += dp[index][i-1];
        if(index!==0)dp[index][i] += dp[index-1][i];
        if(i!==0 && index!==0)dp[index][i]-=dp[index-1][i-1];
    })
})
input.forEach(([x1,y1,x2,y2])=>{
    let sum = dp[x2-1][y2-1];
    if (x1 !== 1) sum -= dp[x1 - 2][y2 - 1];
    if (y1 !== 1) sum -= dp[x2 - 1][y1 - 2];
    if (x1 !== 1 && y1 !== 1) sum += dp[x1 - 2][y1 - 2];
    answer+=`${sum}\n`;
})
console.log(answer.trim());

 

풀이방법

이 문제는 Dynamic Programming을 이용하여 푸는 문제이다.

dp라는 2D Array를 input으로 주어진 N x N matrix로 변환한다.(deep copy이용)

dp의 각 위치에는 (1,1)부터 (x,y)만큼의 값들의 합을 값으로 한다.

이후 (x2,y2)의 위치의 값에서 x1!==1인 경우 dp[x1 - 2][y2 - 1]을 빼고 y1!==1인 경우 dp[x2 - 1][y1 - 2]을 빼며 두 조건을 모두 만족하는 경우에 중복해서 빼준 dp[x1 - 2][y1 - 2]을 더해줍니다.

 

 

느낀점
두 가지 부분에서 고치는 데 어려움을 겪었다.

한 가지는 이전부터 (x,y)의 좌표를 무조건 적으로 columns는 x로, row는 y로 계산하던 버릇덕분에 어디서 틀렸는지 계속 고생하였다.

다른 한 가지는 2D Array의 deep copy 부분이었다. 나는 완전한 deep copy가 아닌 slice 메서드를 이용한 불완전한 deep copy하고 있었기에 중간 계산에서 계속 오류가 발생했다.

 

deep copy부분은 제 다른 글을 참고해 주시면 감사하겠습니다.(https://hopedevelopment.tistory.com/50)