부분합 알고리즘이란?
- 연속된 값의 합을 직접 더하지 않고, 시작과 끝점 다음점에 기록한 다음 마지막에 합계를 구하는 알고리즘
- 연속된 값의 합이 여러개 있을 때 부분합 알고리즘을 사용할 수 있음
알고리즘 동작 과정
- 모든 부분합을 배열에 기록한다. 이 때 [a, b] 구간에서 c를 더해야 하는 경우 array[a] += c, array[b] -=c 를 해준다.
- 가령 길이가 8인 배열 [0, 0, 0, 0, 0, 0, 0, 0]이 있다 해보자.
- 구간 [1, 4]까지 3의 값을 더하고 싶다. 그렇다면 array[0] += 3, array[5] -= 3을 하여 배열을 [0, 3, 0, 0, 0, -3, 0, 0]이 으로 만들어준다.
- 0부터 시작해 현재 위치의 배열의 값을 이전 위치의 배열 값과 더해준다.
- 이 과정을 진행하면 배열은 [0, 3, 3, 3, 3, 0, 0, 0]이 되어 의도한 부분합을 얻을 수 있게 된다.
- 배열에 덧셈을 해야하는 연산이 많아질수록 연산량을 많이 줄일 수 있다는 장점을 가진다.
예시
문제
N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.
적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.
예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.
첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.
두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다.
세 번째로 아군이 맵의 (1,0)부터 (3,1)까지 회복하여 2만큼 건물의 내구도를 높이면 아래와 같이 2개의 건물이 파괴되었다가 복구되고 2개의 건물만 파괴되어있는 상태가 됩니다.
마지막으로 적이 맵의 (0,1)부터 (3,3)까지 공격하여 1만큼 건물의 내구도를 낮추면 아래와 같이 8개의 건물이 더 파괴되어 총 10개의 건물이 파괴된 상태가 됩니다. (내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락하는 것에 유의해주세요.)
최종적으로 총 10개의 건물이 파괴되지 않았습니다.
건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.
제한사항
1 ≤ board의 행의 길이 (= N) ≤ 1,000
1 ≤ board의 열의 길이 (= M) ≤ 1,000
1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
1 ≤ skill의 행의 길이 ≤ 250,000
skill의 열의 길이 = 6
skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
type은 1 혹은 2입니다.
type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
(r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
0 ≤ r1 ≤ r2 < board의 행의 길이
0 ≤ c1 ≤ c2 < board의 열의 길이
1 ≤ degree ≤ 500
type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
type이 2이면 degree만큼 건물의 내구도를 높입니다.
건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.
입출력 예시
board = [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] 이고, skill = [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 인 경우 10개의 건물이 파괴되지 않는다.
board = [[1,2,3],[4,5,6],[7,8,9]] 이고, skill = [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 인 경우 6개의 건물이 파괴되지 않는다.
풀이
- 앞선 예시와 다르게 배열이 2차원이다. 이 경우에는 어떻게 해야 할까?
- 가령 길이가 5 * 5인 배열에서 (1, 1), (3, 3)에 1을 더한다 가정해보자.
- 계산의 편의를 위해 한방향씩 가로 방향의 누적합을 구하고, 세로방향의 누적합을 구한다 해보자. 그렇다면 가로합이 끝났을 때 배열은 다음과 같아야 한다.
[
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, -1, -1, -1, 0]
]- 이 배열을 만들어내기 위해서는 처음 배열은 다음과 같아야 한다.
[
[0, 0, 0, 0, 0],
[0, 1, 0, 0, -1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, -1, 0, 0, 1]
]- 즉 (a, b), (c, d) 구간에 n의 값을 더하는 경우에는 array[a, c], array[b + 1, d+ 1]에 n을 더하고, array[a, d + 1], array[b + 1, c]에 n을 빼준 값을 기록하면 된다.
function solution(board, skill) {
// 누적합을 기록할 배열
const map = Array.from({length: board.length}, () => new Array(board[0].length).fill(0));
skill.forEach(e => {
const [type, r1, c1, r2, c2, degree] = e;
// 문제에 맞게 부분합 기록
if (type === 1) {
// 시작점과 끝점은 의도한 값대로, 두 꼭지점이 교차하는 나머지 두점은 의도한 값을 반대로 기록함
map[r1][c1] -= degree;
if (r2 !== board.length - 1) map[r2 + 1][c1] += degree;
if (c2 !== board[0].length - 1) map[r1][c2 + 1] += degree;
if (r2 !== board.length - 1 && c2 !== board[0].length - 1) map[r2 + 1][c2 + 1] -= degree;
} else {
map[r1][c1] += degree;
if (r2 !== board.length - 1) map[r2 + 1][c1] -= degree;
if (c2 !== board[0].length - 1) map[r1][c2 + 1] -= degree;
if (r2 !== board.length - 1 && c2 !== board[0].length - 1) map[r2 + 1][c2 + 1] += degree;
}
});
// 가로, 세로 순으로 부분합 누적계산
for (let i = 0;
i < board[0].length; i++) {
for (let j = 1; j < board.length; j++) map[j][i] += map[j - 1][i];
}
for (let i = 0; i < board.length; i++) {
for (let j = 1; j < board[0].length; j++) map[i][j] += map[i][j - 1];
}
// 건물에 주어진 데미지를 받고 건물 체력이 0보다 크면 파괴되지 않은 건물
let answer = 0;
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
if (board[i][j] + map[i][j] > 0) answer++;
}
}
return answer;
}