[백준 / BOJ] 16967 배열 복원하기

문제

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

16967번: 배열 복원하기

크기가 H*W인 배열A를 아래로 X 오른쪽으로 Y만큼 이동한 배열을 배열 A와 겹쳤을때 나온 배열을 배열 B라고 하자.

(배열이 겹쳐지면 같은 위치의 수가 합쳐진다.)

 

배열의 크기 H, W 이동범위 X, Y, 배열 B가 주어질때 배열 A를 구하는 문제다.

 

---

풀이

수학? 구현? 문제다.

 

배열B가 주어졌을때, 원래 배열의 (i,j)의 값은 다음과 같이 구할수있다.

A[i][j] = B[i][j] - A[i-X][j-Y];

단 이때, i-X, j-Y가 범위를 벗어난다면,(0보다 작아진다면) 

A[i][j] = B[i][j];

가 된다.

 

배열의 크기만큼 반복하면 되므로,

시간복잡도는 O(H*W)가 된다.

 

소스코드

    private void setAns(){
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                if(outOfIndex(i-Down,j-Right)) ans[i][j] = arr[i][j];
                else ans[i][j] = arr[i][j] - ans[i-Down][j-Right];
            }
        }
    }

 

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/16967%20%EB%B0%B0%EC%97%B4%20%EB%B3%B5%EC%9B%90%ED%95%98%EA%B8%B0/Main.java

devxb/JJUNalgo