문제

파괴되지 않은 건물
N x M 크기의 게임 맵이 있고, 각 칸에는 내구도를 가진 건물이 있다.
이 건물들을 skill들을 사용하여 건물들의 내구도를 변경시킨다.
최종적으로 건물들의 내구도가 1 이상인 갯수를 찾는다.

아이디어

핵심 아이디어

1. 2차원 배열 board의 구간 (r1, c1) ~ (r2, c2)에 값을 N을 채우고 싶다면 다음 4구역에 값을 다음과 같이 채운다.
   1) 4x8크기의 배열의 (0, 2) ~ (2, 5)구간에 값 3을 채우고 싶다.
   2) board[0][2], board[3][6]에 값 3, board[3][2], board[0][6]에 값 -3을 넣는다.
   3) row를 고정하고 col을 1씩 증가시키며 이전 방문했을 때의 값을 더한다.

4) col을 고정하고 row를 1씩 증가시키며 이전 방문했을 때의 값을 더한다.

5) 최종적으로 원하는 구역만큼 값을 채워 넣을 수 있다.

2. board[r1][c1], board[r2 + 1][c2 + 1] = N, board[r1][c2 + 1], board[r2 + 1][c1] = -N을 넣고, 가로로 이동하며 이전의 값을 누적, 세로로 이동하며 이전의 값을 누적시킨다.
3. 모든 skill에 대해 sheet를 미리 채워두고, 마지막에 누적합을 한번 하게 된다면 시간 복잡도 O(K + NM) 이 될 수 있다.

풀이 아이디어

1. 모든 스킬이 끝난 후, 건물들의 내구도 변화량을 sheet배열을 만들어 사용한다.
2. type의 값에 따라 d에 -1을 곱할지 말지 정한 후, 누적합 초기 세팅을 한다.
3. 핵심 아이디어의 1-1 ~ 1-2 과정을 모든 skill에 대해 반복하여 sheet의 값을 채워둔다.
4. skill을 모두 사용한 후, sheet테이블에 누적합(1-3 ~ 1-5)을 진행한다.
5. 초기 건물들의 내구도 board에 내구도 변화량 sheet를 더하여 결과값을 계산한다.

풀이

def make_sheet(sheet: list, skill: list) -> list:
    t, r1, c1, r2, c2, d = skill
    if t == 1: d *= -1
    sheet[r1][c1] += d
    sheet[r1][c2 + 1] += d * -1
    sheet[r2 + 1][c1] += d * -1
    sheet[r2 + 1][c2 + 1] += d


def solution(board, skills):
    answer = 0
    sheet = [[0 for _ in range(len(board[0]) + 1)] for _ in range(len(board) + 1)]
    for skill in skills:
        make_sheet(sheet, skill)

    for c in range(len(board[0])):
        for r in range(1, len(board)):
            sheet[r][c] += sheet[r - 1][c]

    for r in range(len(board)):
        for c in range(1, len(board[0])):
            sheet[r][c] += sheet[r][c - 1]

    for r in range(len(board)):
        for c in range(len(board[0])):
            board[r][c] += sheet[r][c]
            if board[r][c] > 0:
                answer += 1

    return answer

유사한 문제

https://programmers.co.kr/learn/courses/30/lessons/72414