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

문제 요약

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

 

skill에 [type, r1,c1,r2,c2,degree]가 주어졌을 때,

board[r1][c1] 부터 board[r2][c2]까지 type==1일 때는 degree만큼 빼주고 type==2일 때는 더해준다.

skill의 모든 행을 수행했을 때 board값이 1보다 큰 건물의 개수를 반환한다.

 

접근

한참을 고민해봐도 3중 for문을 사용하는 방법밖에 떠오르지 않았다.

결국 찾아보니 누적합을 사용해서 풀 수 있다는 것을 알았다.

이런 방법을 어떻게 생각해내지..? 정말 신세계였다. 내가 바본가;;

처음에는 코드랑 설명을 같이 봐도 이해가 되지 않았는데 직접 예시로 그림을 그려보니 이해가 갔다. 

 

 

코드

def solution(board, skill):
    answer = 0

    r = len(board)
    c = len(board[0])

    tmp = [[0] * (c + 1) for _ in range(r + 1)]
    for typ, r1, c1, r2, c2, degree in skill:
        if typ == 1:
            degree = -degree

        tmp[r1][c1] += degree
        tmp[r2 + 1][c1] -= degree
        tmp[r1][c2 + 1] -= degree
        tmp[r2 + 1][c2 + 1] += degree
        
    for i in range(r):
        for j in range(1, c):
            tmp[i][j] += tmp[i][j - 1]

    for j in range(c):
        for i in range(1, r):
            tmp[i][j] += tmp[i - 1][j]

    for i in range(r):
        for j in range(c):
            if board[i][j] + tmp[i][j] >= 1:
                answer += 1

    return answer