문제 설명
•
내구도를 가진 건물들이 있는 N x M 게임 맵에서 적의 공격과 아군의 회복 스킬이 주어진 후, 파괴되지 않은 건물의 개수를 구하는 문제
예제 입력/출력
board | skill | result |
[[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] | [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] | 10 |
[[1,2,3],[4,5,6],[7,8,9]] | [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] | 6 |
제약 조건
•
•
◦
각 건물의 내구도
•
◦
type 1 적의 공격 → 내구도를 낮춤.
◦
type 2 아군의 회복 → 내구도를 올림.
문제 풀이
풀이1 브루트 포스 -
풀이2 그리디
풀이3 DP -
풀이 코드
def solution(board, skill):
N = len(board) # 세로
M = len(board[0]) # 가로
# Solve (DP 차이 배열)
dp = [[0 for _ in range(M + 2)] for _ in range(N + 2)] # 1-index
for type, r1, c1, r2, c2, degree in skill:
if type == 1:
degree = -degree
r1, c1, r2, c2 = r1 + 1, c1 + 1, r2 + 1, c2 + 1
dp[r1][c1] += degree
dp[r1][c2 + 1] -= degree
dp[r2 + 1][c1] -= degree
dp[r2 + 1][c2 + 1] += degree
for y in range(1, N + 1):
for x in range(1, M + 1):
dp[y][x] += dp[y - 1][x] + dp[y][x - 1] - dp[y - 1][x - 1]
ans = 0
for y in range(N):
for x in range(M):
ans += (board[y][x] + dp[y + 1][x + 1] > 0)
return ans
Python
복사