문제 설명
N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.
적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.
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일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
(r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
0 ≤ r1 ≤ r2 < board의 행의 길이
0 ≤ c1 ≤ c2 < board의 열의 길이
1 ≤ degree ≤ 500
type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
type이 2이면 degree만큼 건물의 내구도를 높입니다.
건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.시간 초과 코드
def action(add_board,n:int,m:int,r1:int,c1:int,r2:int,c2:int,degree:int):
# 시간 복잡도는 O(n), 참고로 n은 행의 길이, m은 열의 길이이다.
# 누적합을 활용했으므로 o(m)은 사라졌다.
for i in range(r1,r2+1):
add_board[i][c1]+=degree
if c2+1<m:
add_board[i][c2+1]-=degree
def solution(board, skill):
answer = 0
n=len(board)
m=len(board[0])
# 브루트 포스를 사용하게 되면 스킬 하나 시전할 때마다 O(N^2)이 소요된다.
# 따라서 최악의 경우, O(25만)*O(1000)*O(1000)이 걸린다.
# 즉, O(len(skill)*n*m)의 시간 복잡도가 걸린다.
# O(n*m)을 O(N^2)이라 할 때, O(N) 또는 O(logN)으로 줄일 필요가 있다.
# 다음은 열에 대한 반복을 피하기 위해 만든 누적합용 배열이다.
add_board=[[0]*m for _ in range(n)]
# 누적합 배열을 활용하면 O(len(skill))*O(n)
for skill_type,r1,c1,r2,c2,degree in skill:
if skill_type==1:
action(add_board,n,m,r1,c1,r2,c2,-degree)
else:
action(add_board,n,m,r1,c1,r2,c2,degree)
# O(n*m)
for i in range(n):
for j in range(1,m):
add_board[i][j]+=add_board[i][j-1]
# o(n*m)
for i in range(n):
for j in range(m):
board[i][j]+=add_board[i][j]
if board[i][j]>0:
answer+=1
# 총 시간 복잡도 = O(len(skill))*O(n)+ O(n*m)+O(n*m)
return answer1차원 배열에 대해 누적합을 적용한 코드이다. 열의 길이 m에 대한 시간 복잡도를 없앨 수 있지만, 시간 초과가 난다.
참고 링크 (공식 해설)
위 링크를 참고해서 해설하면 풀이 원리는 다음과 같다. 입력을[1,0,0,3,4,4]라고 하자. 그리고 board를 입력 1의 초기 상태와 같다고 하자. 그러면 action 함수에 의해 add_board 배열은 다음과 같이 나온다.
-4 0 0 0 0
-4 0 0 0 0
-4 0 0 0 0
-4 0 0 0 0입력 [1,2,0,2,3,2]를 적용하면 add_board는
-4 0 0 0 0
-4 0 0 0 0
-6 0 0 0 2
-4 0 0 0 0 입력 [2,1,0,3,1,2]를 하면
-4 0 0 0 0
-2 0 -2 0 0
-4 0 -2 0 2
-2 0 -2 0 0 입력 [1,0,1,3,3,1]를 하면
-4 -1 0 0 1
-2 -1 -2 0 1
-4 -1 -2 0 3
-2 -1 -2 0 1 이 된다.
이에 대해
for i in range(n):
for j in range(1,m):
add_board[i][j]+=add_board[i][j-1] 를 적용하여 실제로 누적합을 진행해보면
-4 -5 -5 -5 -4
-2 -3 -5 -5 -4
-4 -5 -7 -7 -4
-2 -3 -5 -5 -4 이 된다. 이에 대해
for i in range(n):
for j in range(m):
board[i][j]+=add_board[i][j]를 적용하면 입력 1의 출력 결과와 동일하다.
1 0 0 0 1
3 2 0 0 1
1 0 -2 -2 1
3 2 0 0 1 정답 코드
def action(add_board,n:int,m:int,r1:int,c1:int,r2:int,c2:int,degree:int):
# 이차원 배열로 확장할 경우 각 action()당 시간 복잡도는 O(1)
add_board[r1][c1]+=degree
add_board[r1][c2+1]-=degree
add_board[r2+1][c1]-=degree
add_board[r2+1][c2+1]+=degree
def solution(board, skill):
answer = 0
n=len(board)
m=len(board[0])
add_board=[[0]*(m+1) for _ in range(n+1)]
# 이차원으로 확장을 적용한 누적합 배열을 활용하면 O(len(skill))*O(1)
for skill_type,r1,c1,r2,c2,degree in skill:
if skill_type==1:
action(add_board,n,m,r1,c1,r2,c2,-degree)
else:
action(add_board,n,m,r1,c1,r2,c2,degree)
# 위에서 아래로 누적합 O(n*m)
for j in range(m):
for i in range(n):
add_board[i+1][j]+=add_board[i][j]
# 왼쪽에서 오른쪽으로 누적합 O(n*m)
for i in range(n):
for j in range(m):
add_board[i][j+1]+=add_board[i][j]
# O(n*m)
for i in range(n):
for j in range(m):
board[i][j]+=add_board[i][j]
if board[i][j]>0:
answer+=1
# 전체 시간 복잡도 = O(n*m*3)+O(len(skill))
return answer공식 해설을 참고해서 풀었다.
원하는 범위가 다음과 같다고 할 때,
n n n
n n n
n n n 일차원으로만 누적합을 하면 다음 예시와 같다. (크기가 커진 것은 패딩 때문)
n 0 0 0 -n
n 0 0 0 -n
n 0 0 0 -n
n 0 0 0 -n이를 이차원으로 확장해서 하면 다음과 같다. (이 역시 크기가 커진 것은 패딩 때문)
n 0 0 0 -n
0 0 0 0 0
0 0 0 0 0
-n 0 0 0 n위 이차원 누적합 배열에 위에서 아래로 합한 후 , 왼쪽에서 오른쪽으로 합하면 원하는 범위를 구할 수 있다고 한다.
아마 혼자 계속 끙끙댔으면 절대 못풀 문제였다.
해설을 보고 생각의 범위를 넓힐 수 있었다!
