[백준 16967번] 배열 복원하기 (C++)

문제링크 : https://www.acmicpc.net/problem/16967

16967번: 배열 복원하기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int H, W, X, Y;
int arr[601][601];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> H >> W >> X >> Y;
    for(int i=0; i<H+X; i++) //변화한 배열 입력
    {
        for(int j=0; j<W+Y; j++)
        {
            cin >> arr[i][j]; 
        }
    }

    for(int i=X; i<H; i++) //복원
    {
        for(int j=Y; j<W; j++)
        {
            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;
}

단순 구현 문제이다.

 

기존 배열을 주어진 조건에 따라 이동하여 만들어진 배열에 대해 중복하여 더해진 것 만큼 빼주면 된다.

<예제>
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+1) (7+2) (8+3) (0+4)
  (0+5) (0+6) (0+7) (0+8)

<복원>
1 2 3 4
5 6 7 8

첫 열을 기준으로 X, Y만큼 이동하여 겹친 부분을 더해주므로 반복문으로 인덱스 위치를 X, Y부터 시작하여 arr[i-X][j-Y]만큼을 빼주면 된다.

그러면 더해줬던 만큼 다시 위에서부터 빼주게 되어 배열을 복원하게 된다.