2022 카카오 코딩테스트 lv.3 파괴되지 않은 건물 파이썬

def solution(board, skill):
    R,C = len(board),len(board[0])
    imos = [[0]*(R+1) for _ in range(C+1)]
    for type,r1,c1,r2,c2,degree in skill:
        if type == 1:
            imos[r1][c1] -= degree
            imos[r1][c2+1] += degree
            imos[r2+1][c1] += degree
            imos[r2+1][c2+1] -= degree
        if type == 2:
            imos[r1][c1] += degree
            imos[r1][c2+1] -= degree
            imos[r2+1][c1] -= degree
            imos[r2+1][c2+1] += degree

    for i in range(len(imos)):
        for j in range(1,len(imos[0])):
            imos[i][j] += imos[i][j-1]

    for i in range(len(imos[0])):
        for j in range(1,len(imos)):
            imos[j][i] += imos[j-1][i]

    answer = 0

    for i in range(R):
        for j in range(C):
            board[i][j] += imos[i][j]
            if board[i][j] > 0:
                answer += 1

    return answer

imos 알고리즘을 이용한 풀이

imos 알고리즘 자체를 몰랐다. 일차원 누적합을 구하는 방법은 알고 있었지만, 이러한 알고리즘이 있는건 몰랐다.

imos는 누적합을 일차원뿐만 아니라 차원을 확장해서 풀 수 있다. 

2021 카카오 광고삽입 문제에서는 일차원 누적합을 한번 더 누적합을 만들어서 문제를 풀었다.

이 문제는 imos 알고리즘을 이용해서 이차원 누적합을 쉽게 구해서 풀 수 있었다.

가로로 휩쓴 후 세로로 휩쓴다.