[백준 16967 🥈] 배열 복원하기

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

16967번: 배열 복원하기

문제

크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐진다.

즉, 배열 B의 (i, j)에 들어있는 값은 아래 3개 중 하나이다.

• (i, j)가 두 배열 모두에 포함되지 않으면, Bi,j = 0이다.
• (i, j)가 두 배열 모두에 포함되면, Bi,j = Ai,j + Ai-X,j-Y이다.
• (i, j)가 두 배열 중 하나에 포함되면, Bi,j = Ai,j 또는 Ai-X,j-Y이다.

배열 B와 정수 X, Y가 주어졌을 때, 배열 A를 구해보자.

입력

첫째 줄에 네 정수 H, W, X, Y가 주어진다. 둘째 줄부터 H + X개의 줄에 배열 B의 원소가 주어진다.

항상 배열 A가 존재하는 경우만 입력으로 주어진다.

출력

총 H개의 줄에 배열 A의 원소를 출력한다.

제한

• 2 ≤ H, W ≤ 300
• 1 ≤ X < H
• 1 ≤ Y < W
• 0 ≤ Bi,j ≤ 1,000

 

문제 풀이

import sys

h,w,x,y=map(int, sys.stdin.readline().split(' '))
B=[list(map(int, sys.stdin.readline().split(' '))) for _ in range(h+x)]

for i in range(x,h+x):
    for j in range(y,w+y):
        # A 배열과 겹치는 부분
        if i<h and j<w:
            B[i][j]-=B[i-x][j-y]

for i in range(h):
    for j in range(w):
        print(B[i][j], end=' ')
    print('')

1. 배열 A가 HxW 사이즈 배열이면서, 배열 A와 배열 A를 밑으로 X칸, 오른쪽으로 Y칸 이동한 배열 A'를 합친 배열 B가 (H+X)x(W+Y) 사이즈 배열임을 통해서 아래와 같은 형식임을 파악할 수 있다.

2. 위와 같은 구조를 가지기 때문에, 겹치는 부분의 좌표가 (i,j)라 했을 때, B[i-x][j-y]를 B[i][j]에서 빼주면 원래 값으로 복원 가능하다.

( 단, 겹치는 부분 중 좌측 상단부터 순서대로 복원해야 함

-> 순서대로 하지 않으면 아직 복원되지 않은 B[i-x][j-y] 값을 B[i][j]에서 빼주게 되므로, 올바르지 않은 값이 저장됨 )

3. 겹치는 부분을 모두 복원해주고 원래 A배열의 위치(B[:h][:w])를 출력해주면 끝