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

문제

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

input

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

output

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

TODO

누적합을 사용한다.

1차원 길이 5의 배열에서 

0~2까지 d로 공격한다고 가정하자.
[0,0,0,0,0] -> [-d,0,0,d,0]
0번에 -d, 2+1(3)번 인덱스에 +d를 넣는다. 

다음 공격은 1~3까지 f로 공격한다고 가정하자. 
[-d,-f,0,d,f] 
1번에 -f, 3+1(4)번 인덱스에 +f를 넣는다.

그리고 모든 스킬을 파악했다면 
전체 딜량을 파악한다. 파악하는 방법은 인덱스 전체 길이에 
arr[index+1] = arr[index] + arr[index+1] 이다. 

첫 공격을 계산해보면 
[-d,-d,-d,0,0]이 나온다.(0~2번까지 d만큼 공격)
두번째 공격을 계산해보면
[-d,(-f-d), (-f-d), -f, 0] 

누적합을 계산할 수 있다. 

2차원 배열의 경우 
(0,0) ~ (2,2)까지 공격한다고 가정하자.
[-d, 0, 0, d, 0]
[ 0, 0, 0, 0, 0]
[ 0, 0, 0, 0, 0]
[ d, 0, 0,-d, 0]
[ 0, 0, 0, 0, 0]
위와 같이 처리하고, 행기준,열기준 누적합을 순서대로 계산한다.
->
[-d,-d,-d,0,0]
[-d,-d,-d,0,0]
[-d,-d,-d,0,0]
[ 0, 0, 0,0,0]
[ 0, 0, 0,0,0]



r1,c1,r2,c2가 전체 배열(NxN)이라고 가정하면 
NxNxlen(skill)을 
NxN의 복잡도(4xlen(skill)+2xNxN)로 해결할 수 있다. 

CODE

def solution(board, skill):
    answer = 0
    N = len(board)
    M = len(board[0])
    temp = [[0 for _ in range(M+1)] for _ in range(N+1)]
    for t,r1,c1,r2,c2,d in skill:
        if t == 1 : 
            d = -d
        temp[r1][c1] += d 
        temp[r1][c2+1] += -d 
        temp[r2+1][c1] += -d 
        temp[r2+1][c2+1] += d 
    
    for i in range(N):
        for j in range(M):
            temp[i][j+1] +=temp[i][j]
            
    for i in range(M):
        for j in range(N):
            temp[j+1][i] += temp[j][i] 
            board[j][i] += temp[j][i]
            if board[j][i] >0 : answer+=1 
    return answer

회고

효율성과 정확도를 맞춰야한다.
정확도를 맞추는것은 정말 간단하게 풀 수 있다.
skill은 type,r1,c1,r2,c2,degree 로 이루어져있는데
type==1이면 공격 type==2이면 힐이다.
r1~r2, c1~c2까지 degree로 공격아니면 힐을 한다.
스킬 들어오는데로 다 더하면 효율성에서 나간다.
효율성에서 안될줄 알앗지만 일단 해봤고 당연히 틀렸다..
그러다 누적합을 보고.. 감동..
참고한 블로그