프로그래머스 파괴되지 않은 건물

이 문제를 읽고서는 처음에는 구현은 너무 쉬운데? 라고 생각했다.
하지만 효율성 테스트가 있는 것을 보고 특정 알고리즘을 사용해 연산을 줄여야 되는구나라고 생각했다.

결론적으로 누적합을 사용한 dp를 사용하면 되는데, 나는 dp를 사용한 풀이를 떠올리지 못했다.
바킹독님의 풀이영상을 보면서 느낀점은 먼저 이분은 연산을 줄이기 위해 뭔가 dp를 사용한 풀이가 있을 것이라고 확신하였고, 그 것을 바탕으로 update query constant라고 검색하셨다고 하였다.
일단 나는 내가 이 문제를 dp를 사용하는 문제인 것을 알았다고 해도 저렇게 검색을 통해 내가 원하고자 하는 dp 풀이법을 찾을 수 있었을까? 라는 의심이 들었다.
나는 누적합을 사용하는 문제를 많이 안풀어봐서 익숙하지도 않았고, 실제 시험을 봤다고 하더라고 저런 워딩을 사용해서 검색하는 방법도 못썼을 것 같다.
결론적으로 이 문제를 통해 고수분들은 저런 사고방식을 가지고 문제에 접근을 하고, 검색하거나 어떤 풀이가 있을까라는 생각을 가지고 문제에 접근하면 좀더 문제를 쉽게 풀 수 있겠다라고 생각했다.

문제 풀이는 구간합을 2차원으로 늘리고, 오른쪽과 아래쪽으로 누적합을 밀어주면 되는 풀이다.

def solution(board, skill):
    answer = 0
    n = len(board)
    m = len(board[0])
    dp = [[0] * m for i in range(n)]
    for sk in skill:
        tp, r1, c1, r2, c2, degree = sk
        if tp == 1: degree = -degree
        dp[r1][c1] += degree
        if c2 + 1 < m:
            dp[r1][c2 + 1] -= degree
        if r2 + 1 < n:
            dp[r2 + 1][c1] -= degree
        if c2 + 1 < m and r2 + 1 < n:
            dp[r2 + 1][c2 + 1] += degree
    for i in range(n):
        for j in range(1, m):
            dp[i][j] = dp[i][j] + dp[i][j - 1]

    for j in range(m):
        for i in range(1, n):
            dp[i][j] = dp[i][j] + dp[i - 1][j]
    for i in range(n):
        for j in range(m):
            board[i][j] += dp[i][j]
            if board[i][j] > 0:
                answer += 1
    return answer