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

파괴되지 않은 건물

설명

N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.

제한사항

• 1 ≤ board의 행의 길이 (= N) ≤ 1,000
• 1 ≤ board의 열의 길이 (= M) ≤ 1,000
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
• 1 ≤ skill의 행의 길이 ≤ 250,000
• skill의 열의 길이 = 6
• skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
• type은 1 혹은 2이며 type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
• type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
• 0 ≤ r1 ≤ r2 < board의 행의 길이
• 0 ≤ c1 ≤ c2 < board의 열의 길이
• 1 ≤ degree ≤ 500
• 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.

건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.

# 느낌이 3중 for문 당연히 안될것 같긴한데
def solution(board, skills):
    answer = 0
#     for skill in skills:
#         for i in range(skill[1], skill[3]+1):
#             for j in range(skill[2], skill[4]+1):
#                 if skill[0] == 1:
#                     board[i][j] -= skill[5]
#                 elif skill[0] == 2:
#                     board[i][j] += skill[5]
#     for row in board:
#         for el in row:
#             if el > 0:
#                 answer += 1
    # 효율성에서 당연히 다 떨어짐 ㅋㅋ
    
    # 모르겠어서 질문하기에 있는 정보 참고해서 부분합에 대해 공부해옴
    
    
    return answer
    

• 안될게 당연하지만 한 번 해봤다.
• 당연히 효율성에서 올 fail

def solution(board, skill):
    answer = 0
    n = len(board) #행
    m = len(board[0]) #열
    board_sum = [[0]*(m+1) for _ in range(n+1)] #누적합 저장하는 배열
    
            
    for ty_pe, r1, c1, r2, c2, degree in skill:
        if ty_pe == 1:
            board_sum[r1][c1] -= degree
            board_sum[r1][c2+1] += degree
            board_sum[r2+1][c1] += degree
            board_sum[r2+1][c2+1] -= degree
        else:
            board_sum[r1][c1] += degree
            board_sum[r1][c2+1] -= degree
            board_sum[r2+1][c1] -= degree
            board_sum[r2+1][c2+1] += degree
                    
    for i in range(n):
        for j in range(1, m):
            #누적합 구하기. 왼쪽에서 오른쪽으로
            board_sum[i][j] += board_sum[i][j-1] #O(n*m)
            
    for i in range(1, n):
        for j in range(m):
            #누적합 구하기. 위에서 아래로
            board_sum[i][j] += board_sum[i-1][j] #O(n*m)
    
    for i in range(n):
        for j in range(m):
            board[i][j] += board_sum[i][j] #O(n*m)
            if board[i][j] > 0:
                answer += 1
        
                   
    return answer

• 진짜 모르겠어서 질문글을 봤는데 누적합이라는 것을 사용한단다.
• 문제는 누적합이 뭔지 모름
• 그래서 검색해봤는데 이해가 잘 안간다.
• 양 모서리에 flag를 놓고 그 상태에서 누적합을 구하면 시간복잡도가 훨씬 효율적이다.
  https://go-ming.tistory.com/m/46
• 해당 링크를 참조하였음