[프로그래머스] 파괴되지 않은 건물 - 파이썬/누적합

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

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

    for s in skill:

        if s[0]==1:
            dgree = -s[5]
        else:
            dgree = s[5]
        graph[s[1]][s[2]] += dgree
        graph[s[3]+1][s[2]] -= dgree
        graph[s[1]][s[4]+1] -= dgree
        graph[s[3]+1][s[4]+1] += dgree

    for i in range(N+1):
        for j in range(1,M+1):
            graph[i][j] += graph[i][j-1]

    for j in range(M+1):
        for i in range(1,N+1):
            graph[i][j] += graph[i-1][j]


    for i in range(N):
        for j in range(M):
            board[i][j]+=graph[i][j]
            if board[i][j]>0:
                answer +=1
                
    return answer

단순하게 반복할 경우 반복문이 3개가 겹쳐서 시간 초과가 발생한다.

그렇기때문에 스킬을 우선적으로 계산하고 그 결과를 board에 넣는 방식으로 접근해야한다.

스킬을 우선적으로 계산하는 방법은 누적합에서도 imos법으로 계산할 수 있다.