백준 16967 배열 복원하기 C++

백준 배열 복원하기 16967 C++

---

문제

크기가 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
  

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

---

전체 코드

#include <iostream>
using namespace std;

int arr[1000][1000]; // 입력받은 B
int main(void)
{
    int H, W, X, Y;
    cin >> H >> W >> X >> Y;

    // B 배열 입력
    for (int i = 0; i < H + X; i++)
    {
        for (int j = 0; j < W + Y; j++)
        {
            cin >> arr[i][j];
        }
    }

    // A 배열 복원
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            if (i >= X && j >= Y) // 겹치는 영역일 때
            {
                arr[i][j] -= arr[i - X][j - Y];
            }
        }
    }

    // 출력
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cout << arr[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

---

결론

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