문제 보기 · Level 3 · 2022 KAKAO BLIND RECRUITMENT · 정답률 45% · 푼 사람 7,471명 (2026-09-30 기준)1
문제
N×M 격자의 칸마다 내구도를 가진 건물이 있다. 스킬 [type, r1, c1, r2, c2, degree]는 (r1, c1)부터 (r2, c2)까지 직사각형 안의 모든 건물 내구도를 degree만큼 낮추거나(type 1, 공격) 높인다(type 2, 회복). 내구도가 0 이하가 된 건물도 계속 공격받고 회복받는다. 모든 스킬이 끝난 뒤 내구도가 1 이상인 건물 수를 돌려준다.
- N, M ≤ 1,000, 내구도 ≤ 1,000
- 스킬 최대 250,000개, degree ≤ 500
풀이
막히면 한 단계씩 펼친다.
필요한 개념
누적 합과 차분 배열: 직사각형에 더하기를 모서리 네 칸의 표시로 바꾸고, 마지막에 가로·세로로 한 번씩 누적한다.
1단계 · 작은 예로 손으로 풀기
3×3 격자에서 (0, 0) ~ (1, 1)에 −2를 한다. 칸 네 개가 2씩 줄어든다.
1차원이었다면 “시작 칸에 −2, 끝 다음 칸에 +2”만 적고 나중에 앞에서부터 더했다. 차이만 적어 두고 앞에서부터 더해 값을 되살리는 것은 미적분의 기본정리를 칸 단위로 쓴 것이다. 2차원에서는 이 표시를 줄마다 한다.
- 0행: 0칸에 −2, 2칸에 +2
- 1행: 0칸에 −2, 2칸에 +2
줄 수만큼 표시하는 대신, 이 “줄마다의 표시”를 다시 세로 방향 차분으로 줄이면 모서리 네 칸만 남는다. (0, 0)에 −2, (0, 2)에 +2, (2, 0)에 +2, (2, 2)에 −2다.
2단계 · 가장 단순한 방법과 그 속도
스킬마다 직사각형 안의 칸을 모두 바꾼다. 스킬 하나가 격자 전체(100만 칸)를 덮을 수 있으니, 25만 개면 최악 2,500억 번이다. 정확성 테스트(격자 100×100, 스킬 100개)는 통과해도 효율성 테스트는 못 넘는다.
3단계 · 핵심 아이디어
- 공격은 −degree, 회복은 +degree로 값 v를 정한다.
- (N + 1)×(M + 1) 표시판 D의 네 모서리에 적는다: D[r1][c1] += v, D[r1][c2 + 1] −= v, D[r2 + 1][c1] −= v, D[r2 + 1][c2 + 1] += v.
- 스킬을 모두 적은 뒤, D를 가로로 한 번 누적하고 세로로 한 번 누적한다. 그러면 D[i][j]가 칸 (i, j)의 내구도 변화량이 된다.
- 두 번 누적하면 한 칸의 표시는 그 칸부터 오른쪽 아래 전체로 퍼진다. 그래서 네 모서리의 부호 +, −, −, +는 포함-배제 원리다. 아래쪽 바깥과 오른쪽 바깥을 한 번씩 빼면 둘이 겹친 오른쪽 아래가 두 번 빠진다. (r2 + 1, c2 + 1)의 +v가 이것을 한 번 되돌린다.
- 스킬마다 네 칸만 적으니 스킬 수와 직사각형 크기가 상관없다.
4단계 · 코드 흐름
- 0으로 채운 (N + 1)×(M + 1) 표시판 D를 만든다.
- 스킬마다 v를 정하고 네 모서리에 적는다.
- 행마다 왼쪽에서 오른쪽으로 누적한다.
- 열마다 위에서 아래로 누적한다.
- board[i][j] + D[i][j] > 0인 칸을 센다.
5단계 · 파이썬 코드
from itertools import accumulate
def solution(board, skill):
N, M = len(board), len(board[0])
D = [[0] * (M + 1) for _ in range(N + 1)]
for t, r1, c1, r2, c2, deg in skill:
v = -deg if t == 1 else deg
D[r1][c1] += v
D[r1][c2 + 1] -= v
D[r2 + 1][c1] -= v
D[r2 + 1][c2 + 1] += v
D = [list(accumulate(row)) for row in D] # 가로로 누적
for i in range(1, N + 1): # 세로로 누적
up, row = D[i - 1], D[i]
for j in range(M + 1):
row[j] += up[j]
return sum(1 for i in range(N) for j in range(M) if board[i][j] + D[i][j] > 0)
accumulate(row): 행의 앞에서부터 더한 값을 차례로 준다. [3, 1, 2] → [3, 4, 6].up, row = D[i - 1], D[i]: 윗줄과 이번 줄을 짧은 이름으로 잡아 둔다. 리스트를 복사하지 않고 같은 줄을 가리키므로,row[j] += …는 D를 직접 바꾼다.- 표시판이 한 칸씩 더 큰 까닭은 c2 + 1, r2 + 1이 격자 밖(M, N)일 때도 적을 자리가 필요해서다.
6단계 · 실행 추적
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]]
| 단계 | 0행 | 1행 | 2행 | 3행 |
|---|---|---|---|---|
| 네 모서리 표시 | −2, 0, 2, 0 | 0, −4, 0, 4 | 102, −100, −2, 0 | −100, 104, 0, −4 |
| 가로 누적 | −2, −2, 0, 0 | 0, −4, −4, 0 | 102, 2, 0, 0 | −100, 4, 4, 0 |
| 세로 누적(변화량) | −2, −2, 0, 0 | −2, −6, −4, 0 | 100, −4, −4, 0 | 0, 0, 0, 0 |
변화량을 처음 내구도에 더하면 [[−1, 0, 3], [2, −1, 2], [107, 4, 5]]다. 1 이상인 칸은 3, 2, 2, 107, 4, 5로 6개다. 표시판의 3열과 3행은 누적하면 모두 0이 되고, 답에는 쓰지 않는다.
7단계 · 복잡도와 흔한 실수
스킬 K개를 적는 데 \(O(K)\), 누적 두 번과 세기에 \(O(NM)\)이다. 1000×1000 격자, 스킬 25만 개로 재 보니 0.2초 안팎이었다.
- 표시판을 N×M으로 만들어 r2 + 1이나 c2 + 1에서 범위를 넘는다.
- 네 모서리 중 (r2 + 1, c2 + 1)의 +v를 빠뜨린다. 그러면 직사각형의 오른쪽 아래 바깥이 모두 −v만큼 틀어진다.
- 가로 누적만 하고 세로 누적을 잊는다.
- “파괴된 건물은 더 공격받지 않는다”로 잘못 읽는다. 문제는 0 이하에서도 계속 깎인다고 한다.
-
프로그래머스 스쿨, “파괴되지 않은 건물” (https://school.programmers.co.kr/learn/courses/30/lessons/92344), 2026-09-30 조회. ↩