[PRO] 파괴되지 않은 건물

우선 브루트포스인 $O(N*M*K)$(N,M:최대 1,000, k:최대 250,000)의 시간복잡도로 작성한 코드는 다음과 같다. 이는 효율성 테스트는 통과 못한다.

def solution(board, skill):
    answer = 0
    
    for one_skill in skill:
        skill_type, r1, c1, r2, c2, degree = one_skill
        for i in range(r1, r2+1):
            for j in range(c1, c2+1):
                if skill_type == 1: # 내구도 낮춤
                    board[i][j] -= degree
                else:
                    board[i][j] += degree
            
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] > 0:
                answer +=1
        
    return answer

나는 시간복잡도에서 K가 곱해지는건 어쩔 수 없을 것 같아 N*M을 개선해야겠다고 생각했고, N+M을 만들기 위해 각 행의 총합, 각 열의 총합을 구하는 방식으로 접근해보았으나 풀리지 않았다.

질문하기 탭에서 구간합 + 2차원을 1차원으로 보는 아이디어를 얻고 다시 접근했다.
1차원에서의 접근법을 2차원에도 적용하면 된다.
1차원 방법까지는 직관적이었는데 2차원 방법은 바로 떠올리기 쉽지 않은 것 같다.

def solution(board, skill):
    answer = 0
    N = len(board[0])
    M = len(board)
    
    cumulative_sum = [[0] * (N+1) for _ in range(M+1)]

    for one_skill in skill:
        skill_type, r1, c1, r2, c2, degree = one_skill
        if skill_type == 1: degree*=(-1)
        
        cumulative_sum[r1][c1] += degree
        cumulative_sum[r1][c2+1] -= degree
        cumulative_sum[r2+1][c1] -= degree
        cumulative_sum[r2+1][c2+1] += degree
        
    # 가로 누적합 계산
    for i in range(M):
        for j in range(N):
            cumulative_sum[i][j+1] += cumulative_sum[i][j]
    
    # 세로 누적합 계산
    for j in range(N):
        for i in range(M):
            cumulative_sum[i+1][j] += cumulative_sum[i][j]
    
    for i in range(M):
        for j in range(N):
            if board[i][j] + cumulative_sum[i][j] > 0:
                answer += 1
        
    return answer