문제

https://school.programmers.co.kr/learn/courses/30/lessons/92344

N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.

적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.
예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.

첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다.

세 번째로 아군이 맵의 (1,0)부터 (3,1)까지 회복하여 2만큼 건물의 내구도를 높이면 아래와 같이 2개의 건물이 파괴되었다가 복구되고 2개의 건물만 파괴되어있는 상태가 됩니다.

마지막으로 적이 맵의 (0,1)부터 (3,3)까지 공격하여 1만큼 건물의 내구도를 낮추면 아래와 같이 8개의 건물이 더 파괴되어 총 10개의 건물이 파괴된 상태가 됩니다. (내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락하는 것에 유의해주세요.)

최종적으로 총 10개의 건물이 파괴되지 않았습니다.

건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.

시간 초과 풀이

아이디어

• 그냥 문제에서 시키는 대로 했다.
• 그랬더니 시간 초과가 났고, 아마도 skill이 최대 25만개인데, 보드 최대크기 1000*1000짜리 쿼리가 들어온다고 쳤을 때 시간초과가 날 게 분명하긴 했다.

코드

def solution(board, skill):
    ROW = len(board)
    COL = len(board[0])
    for s in skill:
        type, r1, c1, r2, c2, degree = s
        for r in range(r1, r2+1):
            for c in range(c1, c2+1):
                if type == 1:
                    board[r][c] -= degree
                else:
                    board[r][c] += degree
    answer = 0
    for i in range(ROW):
        for j in range(COL):
            if board[i][j] >= 1: 
                answer += 1
    
    return answer

정답 풀이

2차원의 누적합 → imos법

https://driip.me/65d9b58c-bf02-44bf-8fba-54d394ed21e0

풀이과정

• 누적합을 기록할, 모두 0으로 채워진 2차원 리스트 prefix_sum을 만든다. (원래 board보다 가로 세로 모두 한 칸씩 더 길게 만들었다.)
• 위의 imos법을 활용하여, 문제에서 주어진 r1, c1, r2, c2에 대해서, 그것보다 한 칸씩 더 가서 degree에 대해 +, -를 찍어준 값을 더해준다.
• 모든 쿼리에 대해 위의 과정이 끝났다면, 모든 행에 대해서 싹다 가로로 쓸면서 누적해주고, 모든 열에 대해서 싹다 세로로 쓸면서 누적해준다.
• 마지막으로 prefix_sum의 모든 원소를 돌면서, 해당 칸의 수와 board[i][j]를 합쳤을 때 1 이상이면 answer을 증가시킨다.

코드

def solution(board, skill):
    ROW = len(board)
    COL = len(board[0])
    prefix_sum = [[0] * (COL+1) for _ in range(ROW+1)]
    
    for type, r1, c1, r2, c2, degree in skill:
        prefix_sum[r1][c1] += degree if type == 2 else -degree
        prefix_sum[r1][c2+1] += -degree if type == 2 else degree
        prefix_sum[r2+1][c1] += -degree if type == 2 else degree
        prefix_sum[r2+1][c2+1] += degree if type == 2 else -degree
    
    #가로로 쓸어준다
    for i in range(ROW):
        for j in range(COL):
            prefix_sum[i][j+1] += prefix_sum[i][j]
    
    #세로로 쓸어준다
    for i in range(COL):
        for j in range(ROW):
            prefix_sum[j+1][i] += prefix_sum[j][i]
    
    #마지막으로 파괴되지 않은 것들의 수를 센다
    answer = 0
    for i in range(ROW):
        for j in range(COL):
            if prefix_sum[i][j] + board[i][j] >= 1:
                answer += 1
    
    return answer