💜배열 복원하기

 

 

1. 문제 설명

16967번: 배열 복원하기

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

www.acmicpc.net

원래 배열 A를 수직으로 X, 수평으로 Y만큼 이동시킨 다음 원래 배열 A와 겹쳐서 새로운 배열B를 만든다. 만드는 원리는 다음과 같다.

1. 겹치는 부분은 겹치는 값의 합이다.
2. 안 겹치는 부분은 원래 값 그대로 이다.
3. 원래 존재하지 않았던 새로운 평야의 값으 0이다.

겹쳐진 배열 B가 주어질 때, 원래 배열 A의 값을 구해라.

2. 푸는 방법

새로운 배열 A를 B를 통해서 구할 때, 겹치지 않는 부분은 B값 그대로 넣는다. 그게 원래 A 값이기 때문이다. 겹치는 부분을 B[i][j]라고 할 때, A[i][j] = B[i][j] - A[i-X][j-Y] 이다. 여기서 만드는 중인 A 배열을 빼주는 이유는 다음과 같다. - A[i-X][j-Y]의 의미는 B의 합해진 값에서 자리 이동을 통해 더해진 값을 빼겠다는 의미이다. 근데 B[i][j] - B[i-X][j-Y]를 하면, B[i-X][j-Y]도 이미 두 개의 수가 합해진 값이므로 정확한 답을 구할 수 없기 때문이다. 반면에 어떤 경우라도 A[1][1]은 B[1][1]이다. (조건에서 X,Y는 항상 1보다 크다.) 따라서 [1][1]부터 Stack up 해 나가면 A는 무조건 원래의 순수한 값이 담긴다. 따라서 A를 이용하는 것이 정확한 답을 도출한다.

3. 코드 분석

Copy

import java.util.*;
import java.io.*;

public class Main{

    static int H, W, X, Y;

    static int [][] arrA;
    static int [][] arrB;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());

        arrA = new int[H][W];
        arrB = 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++) {
                arrB[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if(i < X || j < Y){
                    arrA[i][j] = arrB[i][j];
                }
                else{
                    arrA[i][j] = arrB[i][j] - arrA[i-X][j-Y];
                }
            }
        }

        for (int[] temp :
                arrA) {
            for (int temp2 :
                    temp) {
                System.out.print(temp2 + " ");
            }
            System.out.println();
        }

    }
}