문제

파괴되지 않은 건물

정답 코드

def solution(board, skill):
    n, m, cnt = len(board), len(board[0]), 0
    accumulate_sum = [[0 for _ in range(m + 1)] for __ in range(n + 1)]
    for attak_type, y1, x1, y2, x2, degree in skill:
        val = -degree if attak_type == 1 else degree
        accumulate_sum[y1][x1] += val
        accumulate_sum[y2 + 1][x2 + 1] += val
        accumulate_sum[y1][x2 + 1] -= val
        accumulate_sum[y2 + 1][x1] -= val
    for i in range(n + 1):
        for j in range(m):
            accumulate_sum[i][j + 1] += accumulate_sum[i][j]
    for j in range(m + 1):
        for i in range(n):
            accumulate_sum[i + 1][j] += accumulate_sum[i][j]
    return sum([1 for i in range(n) for j in range(m) if board[i][j] + accumulate_sum[i][j] > 0])

풀이

누적합 문제입니다....
이 문제로 처음 누적합이라는 기법을 접했는데요...
자세한 설명은 카카오에서 해주는 설명을 참고하면 매우 좋습니다!

정확성만 맞추고자 하면 매우 쉬운 문제입니다
그냥 이중 for문 몇 번 돌리면 되는 문제죠

하지만 문제는 효율성입니다. 단순히 건물에 대미지를 주거나, 회복을 주는 거르 스킬을 쓸 때마다 모든 건물에 적용시켜주면 효율성이 박살나 버립니다

이럴때 사용하면 되는 기법이 누적합입니다
일종의 다이나믹 프로그래밍 같은 기법이죠.

우선 저는
1. 각 스킬마다 누적합 배열에 더하고 뺄 값val을 설정합니다

a. 회복이면 양수, 공격이면 음수

2. 그리고 스킬을 쓰는 직사각형의 각 모서리에 val을 더하거나 빼 줍니다
   저는 값을 적용시키는 방향을 좌 -> 우, 상 -> 하로 설정했습니다

   a. 좌측 상단, 우측 하단에는 val 값을 더해주고
   b. 좌측 하단, 우측 상단에는 val 값을 빼주었습니다

   여기서 좌측 상단의 값(x1, y1)은 그대로 좌표를 쓰지만, 우측 하단의 좌표(x2, y2)는 각각 사용할 때 마다 +1 해줘야 합니다!!! +1 안하면 가로, 세로 별로 한 칸씩 작은 직사각형에 스킬을 적용한 것과 같습니다!!

3. 모든 스킬을 적용시키고 나면, 이제 스킬 직사각형(accumumlate_sum)에 좌 -> 우, 상 -> 하 로 누적합 시킵니다

4. 그리고 각 배열을 순회하면서 (건물의 초기 HP + 스킬의 총합) 이 양수인 건물만 취합합니다