[ 백준 / 16967번 ] Silver III 배열 복원하기 - SOLVED BY JAVA

www.acmicpc.net/problem/16967

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

제한

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

 

제한이 있어서 편하게 풀 수 있는 문제이다.  

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int H = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		int X = Integer.parseInt(st.nextToken());
		int Y = Integer.parseInt(st.nextToken());
		
		int BX = H+X, BY = W+Y;
		int[][] B = new int[BX][BY];
		for(int i =0; i< BX; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j< BY; j++) {
				B[i][j]= Integer.parseInt(st.nextToken());
			}
		}
		int[][] A = new int[H][W];
		for(int i =0; i< BX; i++) {
			for(int j =0; j< BY; j++) {
				if(i<X && j< W) {// 위쪽 안겹치는 거 
					A[i][j] = B[i][j];
				}else if(j<Y && i<H) { // 왼쪽 안겹치는 거 
					A[i][j] = B[i][j];
				}else if(j>=Y && i>=X  && j< W && i<H) {//겹치는 거 
					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++) {
				System.out.print(A[i][j]+ " ");
			}
			System.out.println();
		}
	}
}

제한 사항을 잘 읽으면 쉽게 풀 수 있다. 

A 배열을 int[H][W]로 선언하고, 

겹치지 않는 부분이 어디인지 잘 찾는다. 

사실 반복문도 H까지만 돌면 된다. 

예제를 보면서 보면. 

초록색으로 체크한 부분은 바로 A[i][j]에 저장해 두고, 

회색으로 체크된 부분은 B[i][j]에서 A[i-X][j-Y]를 하게 되면 풀 수 있는 문제이다. 

실버3이라 크게 어렵지 않은 문제이다. 

효

효율성은 이정도가 나왔다. H까지만 돌면 더 줄지 않을까 생각한다.