[프로그래머스] 파괴되지 않은 건물 (누적합|Python)

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

프로그래머스

 

이것이 누적합이다 !! 를 보여주는 문제이다 ㅋㅋㅋ 

단순하게 구현하면 시간초과가 나므로 누적합을 이용하여 degree 값을 미리 계산해두고 board에 더해주면 된다. 

def solution(board, skill):
    answer = 0
    n = len(board) # col 
    m = len(board[0]) # row 
    dp = [[0] * (m+1) for _ in range(n+1)]

    for t, r1, c1, r2, c2, degree in skill:
        if t == 1: # 공격 
            degree *= (-1) # minus 값으로 변경 
        # dp 에 표시해두기 
        dp[r1][c1] += degree # 영향 받기 시작하는 부분 
        dp[r1][c2+1] -= degree # degree 영향 범위 아닌 부분 
        dp[r2+1][c1] -= degree # degree 영향 범위 아닌 부분 
        dp[r2+1][c2+1] += degree # 두번 빼주는 부분 다시 더해주기 
    
    # 누적합 계산하기 , 세로 방향 
    for i in range(n):
        for j in range(m):
            dp[i+1][j] += dp[i][j]
    
    for i in range(n):
        for j in range(m):
            dp[i][j+1] += dp[i][j]
    
    
    # 파괴되지 않은 건물 
    for i in range(n):
        for j in range(m):
            if board[i][j] + dp[i][j] > 0:
                answer += 1
        
    return answer