[Programmers] Python 파괴되지 않은 건물 (92344)

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

프로그래머스

 

 

누적합을 응용한 문제이다.

누적합 배열을 degree의 값을 응용하는 것으로 쓴다.

def solution(board, skill):
    answer = 0

    M, N = len(board[0]),len(board)
    tile = [[0 for _ in range(M+1)] for _ in range(N+1)]

    for type, r1, c1, r2, c2, degree in skill:
        if type == 1:
            tile[r1][c1] += (-degree)
            tile[r2+1][c2+1] += (-degree)
            tile[r1][c2+1] -= (-degree)
            tile[r2+1][c1] -= (-degree)

        else:
            tile[r1][c1] += degree
            tile[r2+1][c2+1] += degree
            tile[r1][c2+1] -= degree
            tile[r2+1][c1] -= degree


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

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

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

    print(answer)

    return answer

 

회고.

누적합으로 풀지 않아 시간초과가 났었다. 2차원 누적합을 생각하는 발상이 아직 부족한거 같다. 2차원 누적합 문제를 많이 접해봐야겠다.