[백준 16967] 배열 복원하기 - 파이썬

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

💡문제 분석 요약

X칸, Y칸 씩 밀려 겹쳐진 배열을 보고 원래 배열을 구한다.

💡알고리즘 설계

1. 원래 배열 A를 0으로 초기화한다
2. A를 B에서 같은 위치에서 복사한다
3. X칸, Y칸씩 슬라이딩 된 위치에 B에서 A의 값을 뺀 값을 저장한다

💡코드

import sys
input = sys.stdin.readline

H, W, X, Y = map(int, input().split())
B=[]
for i in range(0,H + X):
    B_row = list(map(int, input().split()))
    B.append(B_row)

#1. A를 0으로 초기화
A= [[0 for j in range(W)] for i in range(H)]

#2. A를 B에서 같은 위치에서 복사
for i in range(0, H):
   for j in range(0, W):
      A[i][j]=B[i][j]


#아래로 X칸, 옆으로 Y칸 (옆이 X가 아님 주의)
#3. 겹치는 부분에 A 빼기
for i in range(X, H):
   for j in range(Y, W):
      A[i][j]=B[i][j]-A[i-X][j-Y]

#5. 출력
for i in A:
    for j in i:
       print(j, end=' ')
    print('')


# 내가 만든 테스트 케이스
# 3 3 1 1
# 1 2 3 0
# 4 6 8 3
# 7 12 14 6
# 0 7 8 9

💡시간복잡도

for문을 이중으로 사용하므로 O(N^2)

💡 느낀점 or 기억할 정보

파이썬에서 이중배열을 초기화 할 떄,
A= [[0]*H]*W로 선언하면 배열이 복사되므로 다른 칸의 값을 바꾸면 그 열의 모든 값이 바뀌는 문제가 생긴다.
A= [[0 for j in range(W)] for i in range(H)] 로 for문을 이용해서 선언해야한다.