[BOJ] 16967 배열 복원하기

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

16967번: 배열 복원하기

21.05.14 기준 문제 난이도 실버3

난이도는 실버3인게 맞는데

학회 슬랙에 올라온 질문 덕분에 고민을 많이 했다..

애초에 그 질문 덕분에 문제를 풀게 된 것이긴 하지만

 

우선 내 풀이는

배열 b를 이용해 배열 a의 내용을 최대한 구하고, 값이 구해지지 않은 부분은 또 구해주는 방법인데

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int h, w, x, y; cin >> h >> w >> x >> y;
	vector<vector<int>> b(h + x, vector<int>(w + y));
	for (int i = 0; i < h + x; i++) {
		for (int j = 0; j < w + y; j++) {
			cin >> b[i][j];
		}
	}

	vector<vector<int>> a(h, vector<int>(w, -1));
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (!((x <= i && i < h) && (y <= j && j < w))) {
				a[i][j] = b[i][j];
			}
			if (!((0 <= i && i < h - x) && (0 <= j && j < w - y))) {
				a[i][j] = b[i + x][j + y];
			}
		}
	}

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (a[i][j] == -1) {
				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++) {
			cout << a[i][j] << ' ';
		}
		cout << ENDL;
	}

	return 0;
}

조금 돌아갔다. 굳이 이렇게 할 필요가 없다.

슬랙에 질문이 올라온 코드를 보니 훨씬 풀이가 깔끔했다

 

 

각설하고

그 질문을 보면

 

16967번 배열 복원하기 문제입니다. 위 코드로 먼저 틀렸습니다를 받고 ans 배열을 사용 하지 않고도 풀 수 있겠다 싶어 아래 방식으로 코드를 조금 수정하여 제출 하자 올바른 풀이가 되었습니다. 두 코드의 차이는 새로운 정답 배열을 사용 하는지 여부 제외하곤 동일하다 생각하는데.. 왜 맞게 된 걸까요..

//틀렸습니다 받은 코드
#include<iostream>
using namespace std;
#define endl '\n'

int h,w,x,y;
int arr[601][601];
int ans[301][301];//*****
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin>>h>>w>>x>>y;
	
	for(int i=0;i<h+x;i++){
		for(int j=0;j<w+y;j++){
			cin>>arr[i][j];
		}
	}
	
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(i<x||j<y) ans[i][j]=arr[i][j];//********
			else ans[i][j]=arr[i][j]-arr[i-x][j-y];//*******
		}
	}
	
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cout<<ans[i][j]<<" ";//******
		}
		cout<<endl;
	}
	
	return 0;
}

//맞았습니다!! 받은 코드
#include<iostream>
using namespace std;
#define endl '\n'

int h,w,x,y;
int arr[601][601];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin>>h>>w>>x>>y;
	
	for(int i=0;i<h+x;i++){
		for(int j=0;j<w+y;j++){
			cin>>arr[i][j];
		}
	}
	
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(!(i<x||j<y)) arr[i][j]-=arr[i-x][j-y];
		}
	}
	
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cout<<arr[i][j]<<" ";
		}
		cout<<endl;
	}
	
	return 0;
}

와... 진짜 고민을 많이 했다.. 둘이 뭐가 다를까..

그리고 깨달아서 다음처럼 답변했는데

 

 

반례를.. 찾았습니다..

3 3 1 1
1 1 1 0
1 3 2 1
1 2 3 1
0 1 1 1

답

1 1 1
1 2 1
1 1 1

틀린 코드에서의 출력

1 1 1
1 2 1
1 1 0

23번째 줄

else ans[i][j]=arr[i][j]-arr[i-x][j-y];

이 부분이

else ans[i][j]=arr[i][j]-ans[i-x][j-y];

가 되어야 합니다.
반례와 같은 상황에서 arr[i-x][j-y]도 겹쳐진 부분의 값일 수가 있습니다.
풀이의 흐름을 보면 b 배열의 겹쳐진 부분에서 a 배열의 값을 빼야 하는 것이기 때문에 arr의 값이 아닌 ans의 값을 빼야 하는 것이라고도 볼 수도 있습니다.

두 번째 코드와 다른 점이 없다고 생각했는데,
두 번째 코드는 arr가 ans와 동일하게 업데이트 되고, 첫 번째 코드에서는 그렇지 않다는 게 차이네요...

혹시 더 궁금한 점 있으시면 스레드에 또 질문해주세요!

 

 

아..

이걸 발견하는 데 정말 시간 많이 걸렸다.

발견 하고 나니까 왜 몰랐을까 싶다..