[카카오] 파괴되지 않은 건물
링크
[ 문제에 대한 이해 ]
- 이 맵에는 내구도를 가진 건물이 하나씩 있다. 적은 이 건물들을 공격하여 파괴하려고 한다.
- 반대로 아군은 회복 스킬을 사용하여 건물들의 내구도를 높일 수 있다.
- 적의 공격과 아군의 회복 스킬은 항상 직사각형 모양이다.
- 최종적으로 0 이하로 떨어지지 않으면, 건물이 파괴되지 않았다고 본다.
접근 방법
[ 문제의 조건에 주의한다. ]
board 의 크기는 가로 1000, 세로 1000이므로 총 100만의 시간복잡도를 갖는다. 그리고 skill 내부 요소의 배열은 6이지만, skill의 배열 길이는 25만이므로 100만 * 25만이면 2500억의 시간복잡도를 갖는다.
- 기존 방식이라면, skill 배열의 r1, c1, r2, c2를 이용하여 해당 범위를 채우고, 값을 변화시키는 방식을 말한다. 이 방식은 항상 board의 처음부터 순회하면서 해당 범위에 있는 모든 값을 변화시켜야 하므로, O(n**2)의 시간복잡도를 갖기 때문이다.
[ 따라서 O(1)으로 skill을 처리할 수 있어야 한다. ]
O(1)으로 처리할 수 있는 방법에 대해 생각해본다.
- dp: 일반적으로 해당 경우에서 dp는 누적합을 구하기 위해 많이 사용할 수 있다. 그러나 해당 문제는 누적합을 구하는 문제도 아니다
- 그리디: 그리디적으로 해결할 수 없다. 최적의 해를 구할 수 있는 방법이 없으며, skill degree와 범위에 따라서 해가 달라진다.
[ 2차원 배열에서 누적합 ]
누적합 기술을 사용하면 합을 구하는 시간복잡도를 1차원 더 줄일 수 있다. 1차원에서 누적합의 방법은 다음과 같다.
- 시작 부분과 끝 부분이 정해져있을 때, 시작 부분에 더하고자 하는 값을 더해준다.
- 마지막 부분 + 1번째 인덱스에 더한 값을 빼준다.
ex
1차원 배열에서 누적합을 2번째 인덱스에서 6번째 인덱스까지 구하고자 할 때, 그림을 그리면 다음과 같다.
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
arr = [1, 2, 3 + 2, 4, 5, 6, 7, 8 - 2, 9, 10] # 7번째 인덱스 에서 -2 를 뺀다.이런 방식으로 작성하는 이유는, 0번째 인덱스부터 값을 차례대로 더할 때, 마지막 인덱스 + 1번째 인덱스의 값은 마지막 인덱스까지 더한 값을 더하지 않은 값이 반영되야 하기 때문이다.
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
r1, r2 = 2, 6
arr[r1] += 2
arr[r2 + 1] -= 2이를 2차원 배열로 확장하면 다음과 같다.
r1, c1, r2, c2 범위에서 누적 합을 구한다고 생각하면, 다음의 배열 값을 더해주는 것과 동일하다고 볼 수 있다.
# 2차원 배열에서의 누적합
# 만약 |r2 - r1| = 3, |c2 - c1| = 3일 때,
s = [[5, 0, 0, -5], [0, 0, 0, 0], [0, 0, 0, 0], [-5, 0, 0, 5]]
# 가로로 배열을 더하면 다음과 같다.
arr = [[5, 5, 5, 0], [0, 0, 0, 0], [0, 0, 0, 0], [-5, -5, -5, 0]]
# 다시 세로로 배열을 더하면 다음과 같다.
arr = [[5, 5, 5, 0], [5, 5, 5, 0], [5, 5, 5, 0], [0, 0, 0, 0]]가로 세로 방향으로 모두 더했을 때, 우리가 원하는 구간 합의 결과를 얻을 수 있음을 알 수 있다.
그렇기 때문에 skill 배열을 탐색하며, 다시 r1, c1, r2, c2 구간을 다시 탐색을 하여 값을 더하거나 뺄 필요가 없다. 단지, skill 배열을 탐색하여 빈 배열에 우선 값을 기록해둔 다음, 한번의 탐색으로 해당 값들을 모두 더해준 뒤, 다시 모두 더해준 값을 기존 2차원 배열에 더해서 넣어주면 된다.
틀린 이유
- 구간 합에 대해서 전혀 생각하지 못했다.
- 탐색 시간을 줄일 수 있는 방법 중, dp 와 그리디적으로 해결하는 방법을 생각했는데, 누적합을 2차원 배열에서 탐색할 수 있는 방법에 대해서는 머릿속에 아얘 없었다.
배운 것
- 누적 합에 대해서 정말 많이 부족하다는 것을 깨달았다.
- 그 동안, 누적 합에 대해서 문제에서 가끔 나오면 틀리고 해당 문제를 외우는 식으로 공부했는데, 그렇다 보니까 조금만 응용하는 문제가 나오면 바로 못 푸는 문제가 발생하고 있다.
- 이번 기회에 백준 사이트에서 누적합 관련 문제를 차근 차근 풀어볼 예정이다.
통과 코드
```python
def accumulate(board):
for i in range(len(board)):
for j in range(1, len(board[0])):
board[i][j] += board[i][j - 1]
for i in range(1, len(board)):
for j in range(len(board[0])):
board[i][j] += board[i - 1][j]
def point_score(board, r1, c1, r2, c2, score):
board[r1][c1] += score
board[r1][c2 + 1] -= score
board[r2 + 1][c1] -= score
board[r2 + 1][c2 + 1] += score
def solution(board: list[list[int]], skill: list[list[int]]):
answer = 0
accumulated_board = [[0 for _ in range(1001)] for _ in range(1001)]
# point score on the accumulate board
for s in skill:
t, r1, c1, r2, c2, degree = s
score = degree
if t == 1:
score = -degree
point_score(accumulated_board, r1, c1, r2, c2, score)
# accumulate
accumulate(accumulated_board)
for i in range(len(board)):
for j in range(len(board[0])):
board[i][j] += accumulated_board[i][j]
if board[i][j] > 0:
answer += 1
return answer
```