문제 번호
알고리즘 분류
문제 풀이
누적 합을 이용하여 풀 수 있다.
주어진 문제의 영토의 각 줄마다 가로의 누적합을 구해준다.
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();
특이사항
'Algorithm > BaeKJoon' 카테고리의 다른 글
[JS][백준]17352_여러분의 다리가 되어 드리겠습니다! (0) | 2022.05.26 |
---|---|
[JS][백준]14600_샤워실 바닥 깔기 (Small) (0) | 2022.05.25 |
[JS][백준]6068_시간 관리하기 (0) | 2022.05.17 |
[JS][백준]17845_수강 과목 (0) | 2022.05.17 |
[JS][백준]14503_로봇 청소기 (0) | 2022.05.16 |