[JS][백준]15724_주지수
Algorithm/BaeKJoon

[JS][백준]15724_주지수

문제 번호

 

15724번: 주지수

네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은

www.acmicpc.net

 

 

 

알고리즘 분류

문제 풀이

 누적 합을 이용하여 풀 수 있다. 

주어진 문제의 영토의 각 줄마다 가로의 누적합을 구해준다.

function makeSum(){
  for(let i=0; i<N; i++) {
    let temp = 0;
    for(let j=0; j<M; j++){
      temp += map[i][j];
      sum[i+1][j+1] = temp; 
    }
  }      
}

 세로 누적합을 구해도 상관없다.

 

이제 문제에서 요구하는 영역을 입력받아서 각 줄의 부분합을 더해주면 된다.

for(let i=0; i<arr.length; i++) {        
    const [x1,y1,x2,y2] = arr[i];    
    let ret = 0;
    for(let j=x1; j<=x2; j++) {      
      ret += sum[j][y2] - sum[j][y1-1];
    }
    answer += ret + '\n';
  }

 

각 줄마다 부분합을 구하지않고 넓이의 부분합을 구해서 계산할 수 도 있다. 그때는 'sum [i][j] : 꼭짓점을 (i, j)로 하는 사각형의 넓이'로 두고 문제를 풀 수 있다.

 (x1,y1,x2,y2)가 주어진다고 했을 때 원하는 부분의 넓이는 sum[x2][y2] - sum[x1][y1] - sum[x2][y1] + sum[x1][y1] 이 된다.

2번 빠지는 영역(sum[x1][y1])    
   
    원하는 영역
   

 

 

전체코드

/**
 * 2*10^8
 * 
 * 부분합 문제.
 * 2차원 부분합? 가로줄 부분합? 영역 부분합 구하기(?)
 * 10^6
 * 10^5번 확인. 10^3 줄. 
 */

const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const map = input.slice(1, N + 1).map(_ => _.split(' ').map(Number));
const K = +input[N + 1];
const arr = input.slice(N + 2).map(_ => _.split(' ').map(Number));
let sum = new Array(N+1).fill(null).map(_ => new Array(M+1).fill(0));

function makeSum(){
  for(let i=0; i<N; i++) {
    let temp = 0;
    for(let j=0; j<M; j++){
      temp += map[i][j];
      sum[i+1][j+1] = temp; 
    }
  }      
}
function sol() {
  let answer = '';

  makeSum();
  for(let i=0; i<arr.length; i++) {        
    const [x1,y1,x2,y2] = arr[i];    
    let ret = 0;
    for(let j=x1; j<=x2; j++) {      
      ret += sum[j][y2] - sum[j][y1-1];
    }
    answer += ret + '\n';
  }
  console.log(answer.trim());
}
sol();

특이사항