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

문제

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

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

풀이

1. 누적합 구하기

[EX] (0, 1)에서 (3, 3)까지 2로 채운다고 하자.

모서리가 되는 4개의 점에 각각의 값을 넣는다.

board[0][1] = +2

board[0][4] = -2

board[4][1] = -2

board[4][4] = +2

1) 오른쪽으로 1칸씩 누적하여 더한다.

2) 아래로 1칸씩 누적하여 더한다.

2. 풀이

모든 skill 값들을 sum_board에 저장하고 누적하여 더한다.

board와 sum_board 값을 더하여 0보다 큰 값의 개수를 구한다.

코드

def solution(board, skill):
    # 위/옆로 1칸씩 늘려서 sum_board 만들기
    width, height = len(board[0])+1, len(board)+1
    sum_board = [[0 for j in range(width)] for i in range(height)]
    
    # 파괴/회복 스킬
    for n, i0, j0, i1, j1, w in skill :   
        sum_board[i0][j0] += w * (-1)**n
        sum_board[i0][j1+1] -= w * (-1)**n
        sum_board[i1+1][j0] -= w * (-1)**n
        sum_board[i1+1][j1+1] += w * (-1)**n

    # 오른쪽으로 밀기
    for i in range(height) : 
        for j in range(1, width) : 
            sum_board[i][j] += sum_board[i][j-1]
    
    # 아래로 밀기
    for i in range(1, height) : 
        for j in range(width) : 
            sum_board[i][j] += sum_board[i-1][j]
    
    # arr 값과 비교하기
    answer = 0    
    for i in range(height-1) : 
        for j in range(width-1) : 
            if sum_board[i][j] + board[i][j] > 0 : 
                answer += 1
    return answer