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

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

문제

---

크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐진다.

즉, 배열 B의 (i, j)에 들어있는 값은 아래 3개 중 하나이다.

• (i, j)가 두 배열 모두에 포함되지 않으면, B_i,j = 0이다.
• (i, j)가 두 배열 모두에 포함되면, B_i,j = A_i,j + A_i-X,j-Y이다.
• (i, j)가 두 배열 중 하나에 포함되면, B_i,j = A_i,j 또는 A_i-X,j-Y이다.

배열 B와 정수 X, Y가 주어졌을 때, 배열 A를 구해보자.

 

입력

---

첫째 줄에 네 정수 H, W, X, Y가 주어진다. 둘째 줄부터 H + X개의 줄에 배열 B의 원소가 주어진다.

항상 배열 A가 존재하는 경우만 입력으로 주어진다.

 

출력

---

총 H개의 줄에 배열 A의 원소를 출력한다.

 

제한

---

• 2 ≤ H, W ≤ 300
• 1 ≤ X < H
• 1 ≤ Y < W
• 0 ≤ B_i,j ≤ 1,000

문제 풀이

---

구현 문제.

문제 본문 중 아래에 맞추어 구현하면 된다.

• (i, j)가 두 배열 모두에 포함되지 않으면, B_i,j = 0이다.
• (i, j)가 두 배열 모두에 포함되면, B_i,j = A_i,j + A_i-X,j-Y이다.
• (i, j)가 두 배열 중 하나에 포함되면, B_i,j = A_i,j 또는 A_i-X,j-Y이다.

배열 B의 범위 안에서 반복문을 돌려 (i, j)가 원래의 배열 A와 이를 아래로 X칸, 오른쪽으로 Y칸 움직인 배열 A'의 범위에 속해 있는지 확인한다.

두 배열 모두의 범위에 속해 있다면 위의 경우 중 두번째이므로 A[i][j]= B[i][j] - A[i-X][j-Y]로 표현할 수 있다.

원래의 배열 A에만 속해있다면 그대로 A[i][j] = B[i][j]이다.

A'의 범위에만 속해있다면 B는 A를 아래로 X칸, 오른쪽으로 Y칸 움직인 칸의 값이므로 원래 칸은 A[i-X][j-Y]이다. 따라서 A[i - X][j - Y] = B[i][j]로 표현할 수 있다.

 

아래는 코드.

#include <iostream>
using namespace std;
int H, W, X, Y;

bool isInOrigin(int i, int j)
{
	if (i >= 0 && i < H && j >= 0 && j < W)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool isInMoved(int i, int j)
{
	if (i-X >= 0 && i-X < H && j- Y >= 0 && j-Y < W)
	{
		return true;
	}
	else
	{
		return false;
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> H >> W >> X >> Y;
	int** B = new int*[H + X];
	int** A = new int*[H];
	for (int i = 0; i < H; i++)
	{
		A[i] = new int[W];
		for (int j = 0; j < W; j++)
		{
			A[i][j] = 0;
		}
	}
	for (int i = 0; i < H + X; i++)
	{
		B[i] = new int[W + Y];
		for (int j = 0; j < W + Y; j++)
		{
			cin >> B[i][j];
		}
	}

	for (int i = 0; i < H + X; i++)
	{
		for (int j = 0; j < W + Y; j++)
		{
			if (isInOrigin(i, j) && isInMoved(i, j))
			{
				A[i][j] = B[i][j] - A[i- X][j - Y];
			}
			else if (isInOrigin(i, j))
			{
				A[i][j] = B[i][j];
			}
			else if (isInMoved(i, j))
			{
				A[i - X][j - Y] = B[i][j];
			}
		}
	}
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			cout << A[i][j]<<" ";
		}
		cout << "\n";
	}
	return 0;
}