[BOJ/Python3(파이썬)] 백준 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 = map(int,input().split())

b = [list(map(int, input().split())) for _ in range(h+x)]

a=[[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if i<x or i>=h or j<y or j>=w:
            a[i][j]=b[i][j]
        else:
            a[i][j] = b[i][j]-a[i-x][j-y]

for arr in a:
    print(*arr)

 

결과

 

풀이 과정

이 문제는 겹치는 부분을 어떻게 표현할 지만 찾으면 금방 풀린다고 생각해서 겹치는 부분을 찾는데 집중했습니다.

배열 A를 x,y만큼 이동하고 수가 겹쳐지는 부분은 수가 합쳐집니다. 이렇게 해서 만들어진 배열이 B입니다.

겹쳐지는 부분은 a[i][j]라 할 때 i는 x부터 h라 할 수 있습니다. (x만큼 이동하므로 최소 x부터, 원래 있던 배열과 합쳐져야 하기 때문에 최대 h)

첫 풀이때에는 조건을 if i<x or i>=h and j<y or j>=w: 로 작성해서 문제에서 주어진 테스트 케이스는 통과했지만 결과는 틀렸다고 나와서 당황했습니다.

직접 테스트 케이스를 만들었고 오류를 찾을 수 있었습니다.

입력	출력
3 3 2 2 1 2 3 0 0 4 5 6 0 0 7 8 10 2 3 0 0 4 5 6 0 0 7 8 9	1 2 3 4 5 6 5 5 9

 a[2][0]와 a[2][1]의 경우가 문제이기 때문에 조건을 다시 확인해봤더니 i와 j 둘 중 하나만 조건을 만족해도 겹치지 않는 부분이기 때문에 and가 아닌 or로 수정했습니다. (if i<x or i>=h or j<y or j>=w:)