백준 16967 배열 복원하기 Python

백준 배열 복원하기 16967 Python

---

문제

크기가 H × W인 배열 A와 정수 X, Y가 있습니다.
배열 B는 크기가 (H+X) × (W+Y)이고, 이는 A와 A를 X칸 아래, Y칸 오른쪽으로 이동시킨 배열을 겹쳐서 만든 것입니다.

즉, \(B[i][j]\)는 다음 중 하나입니다.

1. 두 배열 모두 포함되지 않으면 0
2. 두 배열 모두 포함되면 \(B[i][j] = A[i][j] + A[i-X][j-Y]\)
3. 한 배열만 포함되면 \(B[i][j] = A[i][j]\) 또는 \(A[i-X][j-Y]\)

문제는 B와 X, Y가 주어졌을 때 A를 복원하는 것입니다.

---

테스트케이스 1

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

출력
1 2 3 4
5 6 7 8

---

문제 작동 원리

1. 겹치지 않는 부분은 그대로 A[i][j] = B[i][j]입니다.
2. 겹치는 부분(\(i \ge X\) && \(j \ge Y\) && \(i < H\) && \(j < W\))은

   A[i][j] = B[i][j] - A[i-X][j-Y]

   로 구할 수 있습니다.
3. 위 공식을 순서대로 적용하면 A 배열을 복원할 수 있습니다.

---

아이디어

• 핵심은 겹치는 부분만 빼주기입니다.
• 겹치는 조건:

  X ≤ i < H
  Y ≤ j < W
  

• 이때만 빼주고, 그 외에는 그대로 둡니다.

---

전체 코드

H, W, X, Y = map(int, input().split())

arr = []

for _ in range(H + X):
    arr.append(list(map(int, input().split())))

for i in range(H + X):
    for j in range(W + Y):
        if (i >= X and i < H) and (j >= Y and j < W):
            arr[i][j] -= arr[i - X][j - Y]

for i in range(H):
    for j in range(W):
        print(arr[i][j], end=' ')
    print()

---

결론

• 이 문제의 핵심은 겹치는 부분을 조건으로 판별하고, 빼서 원래 A를 구하는 것입니다.
• 겹치지 않는 부분은 단순 복사, 겹치는 부분만 빼주면 정답이 나옵니다.
• 구현 자체는 단순하지만, 겹치는 좌표 조건을 정확히 이해하는 것이 중요합니다.