프로그래머스 [Lv. 3] 파괴되지 않은 건물 {언어 : Python} [다시 풀어 보기]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/92344?language=python3

프로그래머스

정답 코드

def solution(board, skill):
    answer = 0
    n = len(board)
    m = len(board[0])
    
    # 계산을 용이하게 하기 위한 범위 설정
    dp = [[0] * (m+1) for _ in range(n+1)]
    for tp, r1, c1, r2, c2, degree in skill:
        # attack
        if tp == 1:
            degree *= -1
        r2 += 1
        c2 += 1
        
        # 좌상부터 이어져서 우하에는 0이 되어야 하므로 + - - +
        # 좌상, 우상, 좌하, 우하
        dp[r1][c1] += degree
        dp[r1][c2] -= degree
        dp[r2][c1] -= degree
        dp[r2][c2] += degree
        
    # 행 누적
    for i in range(n):
        for j in range(1, m):
            dp[i][j] += dp[i][j-1]
    
    # 열 누적
    for p in range(1, n):
        for q in range(m):
            dp[p][q] += dp[p-1][q]
    
    # 전체 탐색
    for r in range(n):
        for c in range(m):
            if board[r][c] + dp[r][c] >= 1:
                answer += 1
    
    return answer

풀이 방법

• 누적합을 예로 든 것이다.
• 행 누적을 하고 열 누적을 하든 열 누적을 하고 행 누적을 하든 똑같다.

느낀점

• 이런 방식은 떠올리기 힘들고 모르면 최대한 빨리 답을 봐서 눈에 익히는 것이 좋다.