풀이

처음에는 범위 만큼 그냥 더해주는 방식으로 지성빼고 풀었다. 당연히 시간초과가 난다. 이는 Prefix Sum(누적합) 방식을 이용하여 시간 초과를 회피할 수 있다.

먼저 skill의 구간을 새로운 board에 적용한다. 새로운 board를 쓰는 이유는 일반 board는 연속된 합이 아니라 랜덤으로 값이 주어지기 때문에 누적합의 규칙이 깨지기 때문이다. 누적합은 연속된 동일한 수의 합에서만 사용할 수 있다. 적용 하는 방식은 만약 범위가 (r1,c1,r2,c2)라고 주어졌을 때
r1,c1 -> 해당 숫자 더해주기
r1,c2+1 -> 해당 숫자 빼주기
r2+1,c2 -> 해당 숫자 빼주기
r2+1,c2+1 -> 해당 숫자 더해주기
이 방식을 사용한다.
더해준다는 의미는 말 그대로 degree를 type에 맞춰 적용시켜준다는 의미이다. 그러면 왜 끝부분 c2+1, r2+1 부분에 숫자를 빼주는 것인가. 이는 우리가 c2 까지만 누적합을 할 것이기 때문에 c2까지 나중에 합을 하고 c2+1에서 부터는 합을 안해주도록 제약을 거는 것이다. 예를 들면 1차원 배열을 기준으로
c1 : 0
c2 : 3
degree : 2
array [0,0,0,0,0]
라고 할 때 array가 [2,0,0,0,-2] 고 왼쪽에서 부터 오른쪽까지 더해준다면 [2,2,2,2,0]이 된다. 이는 0~3까지 합을 해준 것이다.
위의 법칙을 이용한다면 2차원 배열에서도 똑같이 적용할 수 있다. 하지만 마지막 r2+1,c2+1 의 해당 숫자를 더해주는 법칙이 새로 생겼다. 이는 2차원 배열에서 마지막 값을 둘 다 빼주고, 즉 행에서도 -2를 해주고 열에서 -2를 해주는 값이 총 두번 생기기 때문에 r2+1,c2+1에서 하나를 더해줌으로써 이를 상쇄시켜준다. 따라서 2차원 배열에서는
[n,0,0,-n][0,0,0,0]
[-n,0,0,n]
을 적용시키고 모든 skill에 왼쪽에서부터 오른쪽, 위에서 아래로 n값을 차례로 더해준다. 그렇다면
[n,n,n,0][n,n,n,0]
[0,0,0,0]
이 나온다.
이를 원래 매개변수로 받은 board에 적용시키면 답이 나온다.

코드

def solution(board, skill):
    answer = 0
    bc = len(board[0]) # board 의 컬럼
    br = len(board) # board 의 행
    sum_list = [[0 for _ in range(bc)] for _ in range(br)]
    
    for i in skill:
        ty,r1,c1,r2,c2,degree = i
        if ty==2:
            sum_list[r1][c1] += degree
            r2,c2 = r2+1,c2+1
            if r2<br:
                sum_list[r2][c1] -= degree
            if c2<bc:
                sum_list[r1][c2] -= degree
            if r2<br and c2<bc:
                sum_list[r2][c2] += degree
            
        else:
            sum_list[r1][c1] -= degree
            r2,c2 = r2+1,c2+1
            if r2<br:
                sum_list[r2][c1] += degree
            if c2<bc:
                sum_list[r1][c2] += degree
            if r2<br and c2<bc:
                sum_list[r2][c2] -= degree

    for i in range(br): #왼쪽에서 오른쪽 더함
        for j in range(1,bc):
            sum_list[i][j] += sum_list[i][j-1]
    for i in range(1,br): #위에서 아래로 더함
        for j in range(bc):
            sum_list[i][j] += sum_list[i-1][j]
    for i in range(br): # 보드에 적용
        for j in range(bc):
            board[i][j] += sum_list[i][j]
    for i in range(br): # 0보다 큰 숫자 카운트
        for j in range(bc):
            if board[i][j]>0:
                answer += 1
    return answer