파괴되지 않은 건물 - pYthon

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

프로그래머스

?? 왤캐 쉬워? 하면서 풀었던 문제

1트

타입이1이라면 데미지니까 보드에서 디그리만큼 빼주고 아닐경우는 더해주고 보드를 전체적으로 돌아보면서 0보다 크다면 남아있는벽이므로 answer+=1해주었다. 그랫더니 결과는? 두구두구두구...

def solution(board, skill):
    answer = 0
    for type,r1,c1,r2,c2,degree in skill:
        if type == 1:
            for i in range(r1,r2+1):
                for j in range(c1,c2+1):
                    board[i][j]-=degree
        else:
            for i in range(r1,r2+1):
                for j in range(c1,c2+1):
                    board[i][j]+=degree
    for i in board:
        for j in i:
            if(j>0):
                answer+=1
    return answer

에라이~ㅋㅋㅋㅋ

2트시작

행의 길이 열의길이가 최대 100이라 보고 풀었는데 자세히 보니 1000인 이슈발생!

보드를 다 탐색하는데에서 시간이 O(n**m)걸리기에 단축시킬 방법을 찾기 시작. 

사실 생각을 못하겟다. 그래서 누적합이라는 것을 다시 찾아봤다. 

1. (0,0)에서 2,1)까지 N만큼빼주는 경우임시 테이블을 만들고 이렇게 세팅을 해준다. 

2. 행의 방향으로 누적합을 해주어 하게 되면 이렇게 된다 .

3. 그후 열의 방향으로 누적합을 해주면 

이렇게 임시 테이블이 완성되고 이 완성된것을 우리의 board에 더해주면 끝.

기존의 방식보다 마지막에 한번만 더해주기에 O(1)시간복잠도