[Programmers/Lv. 3/Python] 파괴되지 않은 건물

📎 문제 정보

난이도	Lv. 3
유형	2차원 누적합, 구간 업데이트
언어	Python
플랫폼 / 제목	Programmers / 파괴되지 않은 건물

---

🔍 문제 분석

• board에 건물 내구도가 주어지고, 여러 스킬이 각각 사각형 범위에 일정 수치만큼 내구도를 증감시킨다.
• 모든 스킬을 적용한 뒤, 내구도가 0보다 큰 건물의 개수를 구해야 한다.

---

💡 풀이 아이디어

• (n+1) × (m+1) 크기의 memo 배열을 두고, 스킬마다 사각형의 네 모서리에만 부호를 맞춰 표시한다.
• 이후 memo를 가로 방향 누적합 → 세로 방향 누적합 순으로 두 번 훑으면, 각 칸에 실제로 적용된 변화량이 복원된다.
• 마지막으로 board[y][x] + memo[y][x] > 0인 칸의 개수를 센다.

---

💻 코드

def solution(board, skill):
    n, m = len(board), len(board[0])
    memo = [[0] * (m + 1) for _ in range(n + 1)]

    for s_type, y1, x1, y2, x2, degree in skill:
        if s_type == 1:
            memo[y1][x1] -= degree
            memo[y1][x2 + 1] += degree
            memo[y2 + 1][x1] += degree
            memo[y2 + 1][x2 + 1] -= degree
        else:
            memo[y1][x1] += degree
            memo[y1][x2 + 1] -= degree
            memo[y2 + 1][x1] -= degree
            memo[y2 + 1][x2 + 1] += degree

    for y in range(n + 1):
        for x in range(m + 1):
            if x == 0: continue
            memo[y][x] += memo[y][x - 1]

    for x in range(m + 1):
        for y in range(n + 1):
            if y == 0: continue
            memo[y][x] += memo[y - 1][x]

    answer = 0
    for by in range(n):
        for bx in range(m):
            final_v = board[by][bx] + memo[by][bx]
            if final_v > 0:
                answer += 1

    return answer

 

---

⏱️ 시간/공간 복잡도

시간 복잡도	O(s + n×m)
공간 복잡도	O(n×m)

---

📝 배운 점 / 실수했던 부분

어머, 이게 뭐야!!!!

 

 

처음 코드는 스킬마다 사각형 범위를 직접 이중 for문으로 순회하며 memo에 누적했다.

값을 바로 board에 더하지 않고 memo에 모아뒀다가 나중에 더하기 라는 아이디어 자체는 맞았지만,

기록하는 행위 자체가 이미 사각형 전체를 순회하고 있어서 최적화 효과가 전혀 없었다.

 

핵심은 기록 자체를 O(1)로 만드는 것이였다.

2차원 사각형에서는 네 모서리에 부호를 맞춰 표시하고

가로·세로 누적합을 각각 한 번씩 적용하는 방식으로 확장해야 한다는 걸 새로 배웠다.

 

이때, 부호를 설정할 때 오류가 생기기 좋으니,

부호를 외우기보다 누적합이 어떻게 상쇄되는지 원리로 이해해야 실수를 줄일 수 있을 것 같다.