문제

[프로그래머스] 파괴되지 않은 건물
https://school.programmers.co.kr/learn/courses/30/lessons/92344

풀이

조건

• 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다.
• 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.
• 적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.
• 내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락한다.
• 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 구한다.

풀이 순서

• 누적합을 구해 해결한다.
  • 효율성 테스트를 통과하기 위해서는 명령을 받을 때 마다 매번 누적합을 구하면 안된다.
  • 누적합을 구해야 하는 영역의 네 모서리에만 누적할 값을 기록한 뒤 DP 방식으로 한번에 누적합을 구한다.
  • 이에 대한 설명은 아래 BaaaaaaaarkingDog님 블로그에 자세히 설명되어있다.

    출처: BaaaaaaaarkingDog
    https://blog.encrypted.gg/1031

  • 네 모서리를 기록할 때 원본 배열(board)의 범위를 벗어날 수 있으므로 행, 열의 길이가 1 더 큰 check 배열을 생성해 누적합을 구한다.
  • 가로, 세로로 누적합을 구한 배열(check)과 원본 배열(board)의 각 위치 값을 더해 파괴되지 않은 건물의 개수를 구한다.

코드

Python

def solution(board, skill):
    answer = 0
    row_len = len(board)  # 행 길이
    col_len = len(board[0])  # 열 길이
    
    # 누적합 기록해 놓을 배열 --> 각 모서리 기록할 때 범위 벗어날 수 있어서 크기를 각각 +1 해줌
    check = [[0 for _ in range(col_len + 1)] for _ in range(row_len + 1)]
    # 명령을 순서대로 처리
    for command in skill:
        attack, r1, c1, r2, c2, degree = command
        # 적 공격 -> -degree
        if attack == 1:
            # 누적 차(?)를 구해야 하므로 왼쪽 위, 오른쪽 아래는 (-degree) 해줌
            check[r1][c1] -= degree
            check[r2 + 1][c2 + 1] -= degree
            # 왼쪽 아래, 오른쪽 위는 (+degree) 해줌
            check[r2 + 1][c1] += degree
            check[r1][c2 + 1] += degree
        # 아군 힐 -> +degree
        elif attack == 2:
            # 누적 합을 구해야 하므로 왼쪽 위, 오른쪽 아래는 (+degree) 해줌
            check[r1][c1] += degree
            check[r2 + 1][c2 + 1] += degree
            # 왼쪽 아래, 오른쪽 위는 (-degree) 해줌
            check[r2 + 1][c1] -= degree
            check[r1][c2 + 1] -= degree
    
    # 가로로 누적합
    for i in range(row_len):
        for j in range(col_len):
            check[i + 1][j] += check[i][j]

    # 세로로 누적합
    for j in range(col_len):
        for i in range(row_len):
            check[i][j + 1] += check[i][j]

    # 원본 배열과 누적합 배열을 합치며 정답 계산
    for i in range(row_len):
        for j in range(col_len):
            value = board[i][j] + check[i][j]
            if value > 0:
                answer += 1

    return answer

정리

• SSAFY 교수님께서 누적합을 구할 때 DP를 사용해 시간복잡도를 낮출 수 있는 방법을 알려주셨다.