[프로그래머스][누적합][imos] 파괴되지 않은 건물

파괴되지 않은 건물

코딩테스트 연습 - 파괴되지 않은 건물

 

• 내 풀이
  • 2차원 누적합 imos로 풀어야 안터질거라는 생각
  • 누적합 진행할때 열 부분 먼저 더하고 행 부분 더했음
  • 2차원 누적합 풀이 방법

[알고리즘] 누적합 문제를 효율적으로 풀 수 있는 imos 법

 

def solution(board, skill):
    n, m = len(board), len(board[0])
    prefix_sum = [[0] * (m + 1) for _ in range(n + 1)]

    for type, r1, c1, r2, c2, degree in skill:
        if type == 1:
            prefix_sum[r1][c1] -= degree
            prefix_sum[r2+1][c1] += degree
            prefix_sum[r1][c2+1] += degree
            prefix_sum[r2+1][c2+1] -= degree
        else:
            prefix_sum[r1][c1] += degree
            prefix_sum[r2+1][c1] -= degree
            prefix_sum[r1][c2+1] -= degree
            prefix_sum[r2+1][c2+1] += degree

    for i in range(n+1):
        for j in range(1, m+1):
            prefix_sum[i][j] += prefix_sum[i][j-1]

    for j in range(m+1):
        for i in range(1, n+1):
            prefix_sum[i][j] += prefix_sum[i-1][j]

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

    return answer