[BOJ] 16967 배열 복원하기 Python

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

16967번: 배열 복원하기

배열 복원하기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

2751

1272

1028

45.246%

문제

크기가 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의 원소를 출력한다.

풀이 코드

import sys
input = sys.stdin.readline

h, w, x, y = map(int, input().split())
graph = []
for i in range(h+x):
    graph.append(list(map(int, input().split())))
new_graph = [[-1]*w for _ in range(h)]

change = []
for i in range(x, h):
    for j in range(y, w):
        if new_graph[i-x][j-y] != -1:
            new_graph[i][j] = graph[i][j] - new_graph[i-x][j-y]
        else:
            new_graph[i][j] = graph[i][j] - graph[i-x][j-y]

for i in range(h):
    for j in range(w):
        if new_graph[i][j] == -1:
            new_graph[i][j] = graph[i][j]

for i in range(len(new_graph)):
    print(*new_graph[i])

처음에 겹치는 부분에 대한 로직을 잘못 생각해서 디버깅에 시간이 좀 걸렸다.

그래도 이번엔 종이에 규칙을 하나씩 적어가며 풀었더니 코드를 비교적 빨리 짰던 것 같다.

생각한 것 외의 경우는 없는지 모든 경우의 수를 찾아보며 로직을 짜기 전 반례를 찾아보는 습관을 갖자 !!