폭탄 던지는 태영이 (20543번) - 백준 (BOJ)

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

20543번: 폭탄 던지는 태영이

 

 

백준 - 폭탄 던지는 태영이 (20543번)

 

난이도 : Gold 1

알고리즘&자료구조 : Prefix Sum (누적 합)

시간복잡도 (Time Complexity) : O( N^2 )

---

★ 핵심 Idea ★

 

◎ 누적합으로 생각보다 간단하게 구현할 수 있는 문제이다.

 

N = 5, M = 3일 때,

(0, 0) 좌표에 영향을 미칠 수 있는 폭탄의 위치는 (1, 1) 뿐이다.

 

따라서 (0, 0) 좌표 값을 통해 (1, 1) 위치의 폭탄 값을 구하고,

이전에 구한 폭탄 값들을 바탕으로 누적합을 통해서

다른 폭탄 값들을 구할 수 있다.

 

---

 

< 예제 입력 2 >

N = 5
M = 3

 

문제의 <에제 입력 2> 에서, (N-M+1) 크기의 행과 열만 가져온 <행렬 A>

 

위의 <행렬 A> 앞에 0으로 이루어진 행을 (M-1)개 삽입하고, 직전 (M-1)개의 누적합을 위에서 아래로 차례대로 빼주면서 값을 업데이트 한다.

 

위의 계산 결과 <행렬 B>

 

위의 <행렬 B> 앞에 0으로 이루어진 열을 (M-1)개 삽입하고, 직전 (M-1)개의 누적합을 왼쪽부터 오른쪽으로 차례대로 빼주면서 값을 업데이트 한다.

 

위의 계산 결과 <행렬 C>

 

위의 <행렬 C>의 테두리에 (M-1)/2 만큼의 두께로 0으로 둘러싸주면, 문제의 <예제 출력 2> 가 된다.

 

---

 

< 전체 코드 >

 

import sys
input = sys.stdin.readline


class Inha():
    def __init__(self, N, M):
        board = [[0] * N for _ in range(M-1)] + [list(map(lambda x: -int(x), input().split())) for _ in range(N-M+1)]
        for c in range(N):
            acc = 0
            for r in range(M-1, N):
                board[r][c] -= acc
                acc += board[r][c] - board[r-M+1][c]
        board = board[M-1:]

        board = [[0]*(M-1) + row[:(N-M+1)] for row in board]
        for r in range(N-M+1):
            acc = 0
            for c in range(M-1, N):
                board[r][c] -= acc
                acc += board[r][c] - board[r][c-M+1]
        board = [row[M-1:] for row in board]
        board = [[0]*N for _ in range(M>>1)] + [[0]*(M>>1) + row + [0]*(M>>1) for row in board] + [[0]*N for _ in range(M>>1)]
        self.board = board


if __name__ == '__main__':
    uni = Inha(*map(int, input().split()))
    print('\n'.join(' '.join(map(str, row)) for row in uni.board))