개발 블로그

문제 링크 : www.acmicpc.net/problem/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

접근 방법

프로그램이 시작하면 arrB에 입력을 받고 그 중 (H x W) 만큼만 map배열에 옮긴다. 

그 후, 행은 X부터 H+X 까지 / 열은 Y부터 W+Y까지 돌면서 즉, 배열 A끼리 겹치는 부분에 한해서 요소끼리 뺄셈 연산을 해준다. (겹친 부분 처리)

이때 주의할 점은 A에서 A를 빼야하고, 뺀 결과를 즉시 반영해 배열 값을 갱신하면서 매 행을 진행해나가야 한다는 것이다. 

아래의 예를 들어서 설명해보겠다.

입력이 다음과 같이 주어졌다고 하자.

3 4 1 1
1 2 3 4 0
5 7 9 11 4
9 15 17 19 8
0 9 10 11 12

그럼 배열 B는 아래와 같다.

아래 배열은 map 배열로, (H x W) 만큼 배열 B에서 복사해온것이다. (H x W)만큼을 제외한 곳은 0으로 채웠다.

X=1, Y=1이므로 색으로 표시한 곳이 겹치는 부분이다. 

우리는 배열 A를 쉽게 알 수 있는데, 이 배열 A를 이용해서 거꾸로 생각해보면 코드를 쉽게 구현할 수 있다. 배열 A는 아래와 같다.

이걸 X=1, Y=1만큼 옮겨서 겹친 것을 구현해보면, 다음과 같다. 

매 행을 진행해 나가면서 겹친 부분끼리 뺀 값을 갱신해줘야, 다음 행을 계산할 때 그 값이 반영돼서 올바른 값이 나온다.

다시 말하면, map[1][1]에서 map[1-X][1-Y]를 빼서 map[1][1]을 6으로 갱신해줘야, 그 다음 행의 map[2][2]-map[2-X][2-Y]를 계산할 때 올바르게 11에서 6을 뺄 수 있다. (매 행마다 값을 갱신해주지 않으면 11에서 (6+1) 을 뺀 것으로 계산된다.)

문제에서 주어진 예제로만 생각했을 때는 

for(int row = X; row<=rowB; row++){
        bool chk=false;
        for(int col = Y; col<=colB; col++){
            if(map[row][col] != 0){
                map[row][col] -= map[row-X][col-Y];
                chk = true;
            }
        }
        
        if(!chk) break;
    }

이 코드에서 map[row][col] -= arrB[row-X][col-Y]로 계산해도 결과값이 잘 나와서 어디가 틀린줄 몰랐는데,

배열 A끼리 겹친것이므로 겹친 부분에 대해서는 배열 A끼리 빼줘야하는걸 놓쳐서 틀린것이었다. 

//
//  SM_BOJ16976_배열 복원하기.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/03/25.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>

using namespace std;

int arrB[610][610];
int map[610][610];

int H,W,X,Y;

int main(){
    
    cin >> H >> W  >> X >> Y;
    int rowB = H+X;
    int colB = W+Y;
    
    for(int i = 0; i<rowB; i++){
        for(int j = 0; j<colB; j++){
            scanf("%d", &arrB[i][j]);
            map[i][j]= 0;
        }
    }
    
    for(int i = 0; i<H; i++){
        for(int j = 0; j<W; j++){
            map[i][j] = arrB[i][j];
        }
    }
    
    
    for(int row = X; row<=rowB; row++){
        bool chk=false;
        for(int col = Y; col<=colB; col++){
            if(map[row][col] != 0){
                map[row][col] -= map[row-X][col-Y];
                chk = true;
            }
        }
        
        if(!chk) break;
    }

    
    for(int i = 0; i<H; i++){
        for(int j = 0; j<W; j++){
            printf("%d ", map[i][j]);
        }
        printf("\n");
    }
    

    return 0;
}