Baekjoon 16967 배열 복원하기 JAVA

16967번: 배열 복원하기

문제

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

풀이

새로 생성되는 배열은 최소 우측 하단으로 1,1 만큼 이동하기 때문에 주어진 배열의 첫 행과 첫 열은 원래의 배열의 형태를 가지고 있다.

다르게 생각하면 x, y 만큼 이동한다면 x행 y열만큼은 원래의 형태이다.

이를 이용하여 이동된 배열의 위치를 가져온 후, 동일하게 겹쳐지는 위치를 빼서 본래의 값을 구한다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int h=Integer.parseInt(st.nextToken()),w=Integer.parseInt(st.nextToken()), x=Integer.parseInt(st.nextToken()), y=Integer.parseInt(st.nextToken());
		int [][] a = new int[h+x][w+y], b=new int[h+x][w+y];
		
		for(int i=0;i<h+x;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<w+y;j++)
				b[i][j] = Integer.parseInt(st.nextToken());
		}
		
		for(int i=0;i<x;i++) {
			for(int j=0;j<w;j++)
				a[i][j]=b[i][j];
		}
		
		for(int j=0;j<y;j++) {
			for(int i=0;i<h;i++)
				a[i][j]=b[i][j];
		}
		
		for(int i=x;i<h;i++) {
			for(int j=y;j<w;j++) {
				a[i][j]=b[i][j]-a[i-x][j-y];
			}
		}
		
		for(int i=0;i<h;i++) {
			for(int j=0;j<w;j++)
				bw.write(a[i][j]+" ");
			bw.write("\n");
		}
		bw.close();
	}
	
}