[백준 16967] 배열 복원하기 - JAVA // le_effort

배열 복원하기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	467	235	185	48.556%

문제

크기가 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

예제 입력 1 복사

xxxxxxxxxx
2 4 1 1
1 2 3 4 0
5 7 9 11 4
0 5 6 7 8

예제 출력 1 복사

xxxxxxxxxx
1 2 3 4
5 6 7 8

예제 입력 2 복사

xxxxxxxxxx
3 3 2 1
1 2 3 0
4 5 6 0
7 9 11 3
0 4 5 6
0 7 8 9

예제 출력 2 복사

1 2 3
4 5 6
7 8 9

 

 

 

풀이

주어진 조건에 맞게 해주면 됩니다.

 

기본적인 문제 접근 전략은 a배열과 b배열 2가지만 만듭니다.

 

a배열을 밀어낸 (h+x) X (h+y) 배열은 따로 만들지 않고 인덱스로 관리해줍니다.

 

• (i, j)가 두 배열 모두에 포함되지 않으면, Bi,j = 0이다.

 

이 부분은 배열 b를 순회하는데, b의 값이 0이면 두 배열에 포함 되지 않으니 a배열에 값이 없다고 보면 되니 continue로 넘어갑니다

 

• (i, j)가 두 배열 모두에 포함되면, Bi,j = Ai,j + Ai-X,j-Y이다.

 

문제에서 저희가 구해야 하는 값은 A배열 입니다.

두 배열 모두에 포함되어 있다는 것은 값이 채워져 있다는 것이며

 

Bi,j = Ai,j + Ai-X,j-Y 를

Ai,j = Bi,j - Ai-X,j-Y 로 표현 할 수 있습니다.

 

• (i, j)가 두 배열 중 하나에 포함되면, Bi,j = Ai,j 또는 Ai-X,j-Y이다.

 

이건 두 배열중 하나가 포함 된다고 했으니 범위를 토대로 구해주면 됩니다.

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    
    static int a[][];
    static int b[][];
    static int h,w,x,y;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String [] input = br.readLine().split(" ");
        
        // 원래 a 배열의 크기
         h = Integer.parseInt(input[0]);
         w = Integer.parseInt(input[1]);
        
        // 추가된 a 배열의 크기
         x = Integer.parseInt(input[2]);
         y = Integer.parseInt(input[3]);
        
        
        a = new int[1001][1001];
        b = new int[1001][1001];
        
        
        for(int i=0; i<h+x; i++) {
            input = br.readLine().split(" ");
            for(int j=0; j<w+y; j++) {
                b[i][j] = Integer.parseInt(input[j]);
            }
        }
        
        
        for(int i=0; i<h+x; i++) {
            for(int j=0; j<w+y; j++) {
                int num = b[i][j];
                if(num ==0) {
                    continue;
                }
                
                
                if(isRange(i,j) && isRange(i-x,j-y)) {
                    a[i][j] = num-a[i-x][j-y];
                }
                
                if(isRange(i,j) && !isRange(i-x,j-y)) {
                    a[i][j] = num;
                }
                if(!isRange(i,j) && isRange(i-x,j-y)) {
                    a[i-x][j-y] = num;
                }
                
                
            }
        }
        
        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++) {
                System.out.print(a[i][j]+" ");
            }
            System.out.println();
        }
        
    }
    public static boolean isRange(int x, int y) {
        if(x>=0 && y>=0 && x<h && y<w) {
            return true;
        }
        return false;
    }
}
​