[Python][백준] 20543번 폭탄 던지는 태영이

https://www.acmicpc.net/problem/20543

공부 날짜 : 2023.02.01 ~ 2023.02.02
정답 참조 여부 : X

폭탄이 터지면 폭탄을 중심으로 m*m 영역의 고도가 낮아진다. 폭탄이 터진 후 각 좌표의 고도가 주어질때 폭탄의 위치를 구하는 문제이다.

---

어렵기도 어렵지만 많이 헷갈리고 다시 풀때도 시간이 오래걸릴거 같은 문제였다.

내용이 복잡하긴 하지만 결론을 말하자면 주어지는 데이터는 구간합의 형태로 주어지고 주어진 구간합으로 원본데이터를 복원하는 문제이다.

문제에서 가장 중요한건 태영이는 폭탄의 폭발 범위가 인하대학교를 넘어가게 던지지 않는다.
즉 학교의 바깥쪽에 설치하지 않는다는 얘기이다.
따라서 바깥쪽 m//2의 영역은 0으로 확정되어서 안쪽 영역만 답을 구하면 된다는 뜻이다.

보통 구간합을 구할 때 원본 데이터 -> 누적합 -> 구간합 의 순서로 구하기 때문에 구간합에서 원본 데이터를 복원 할 때도 누적합을 구해야 했다.

# 값을 구하고 누적합을 갱신함
for i in range(n-m+1):
    for j in range(n-m+1):
        answer[i][j] = input_data[i][j] - sum_[i][j] + sum_[i+m][j] + sum_[i][j+m] - sum_[i+m-1][j+m] - sum_[i+m][j+m-1] + sum_[i+m-1][j+m-1]
        sum_[i+m][j+m] = sum_[i+m-1][j+m] + sum_[i+m][j+m-1] - sum_[i+m-1][j+m-1] + answer[i][j]

수식 결과가 좀 많이 길긴 하지만

input_data[i][j] - sum_[i][j] + sum_[i+m][j] + sum_[i][j+m]

이 부분은 누적합에 해당하는 수이고,

 - sum_[i+m-1][j+m] - sum_[i+m][j+m-1] + sum_[i+m-1][j+m-1]
 # == -(sum_[i+m-1][j+m] + sum_[i+m][j+m-1] - sum_[i+m-1][j+m-1])

이 부분이 누적합에서 해당 위치의 값을 구하기 위해 빼고 더해준 값이다.

설명에 그림이 추가적으로 필요할거 같아서 추후 그림을 추가하도록 하겠다.

소스코드

import sys
input = sys.stdin.readline
##################################################
# 문제를 푸는데 필요한 데이터만 남기는 작업
def Set_need_data(list_):
    new_list = [[0 for _ in range(n-m+1)] for _ in range(n-m+1)]

    for i in range(n-m+1):
        for j in range(n-m+1):
            # 양수만 남기기 위해 -값을 저장
            new_list[i][j] = -list_[i][j]

    return new_list

##################################################
n, m = map(int,input().split())

input_data = [list(map(int, input().split())) for _ in range(n)]

input_data = Set_need_data(input_data)

# 누적합이 저장될 2차원 배열
sum_ = [[0 for _ in range(n+1)] for _ in range(n+1)]

# 정답이 저장될 배열 각 변의 0은 제외하고 폭탄 존재 가능한 영역만 남겼다.
answer = [[0 for _ in range(n-m+1)] for _ in range(n-m+1)]

# 값을 구하고 누적합을 갱신함
for i in range(n-m+1):
    for j in range(n-m+1):
        answer[i][j] = input_data[i][j] - sum_[i][j] + sum_[i+m][j] + sum_[i][j+m] - sum_[i+m-1][j+m] - sum_[i+m][j+m-1] + sum_[i+m-1][j+m-1]
        sum_[i+m][j+m] = sum_[i+m-1][j+m] + sum_[i+m][j+m-1] - sum_[i+m-1][j+m-1] + answer[i][j]

# 정답 출력
for i in range(m//2):
    print("0 "*n)

for i in range(n-m+1):
    print("0 "*(m//2) + " ".join(map(str, answer[i])) + " 0"*(m//2))

for i in range(m//2):
    print("0 "*n)