BOJ 2514(자동분무기) 풀이

이미지를 누르면 문제로 이동합니다

 

이 문제는 8 * 8 사이즈의 맵에서 특정 위치에 비료액을 뿌리는 자동 분무기 혹은 제초제를 뿌리는 자동 분무기가 위치해 있다.

비료액 분무기는 해당 위치에서 십자가 모양으로 값을 1씩 더하고, 제초제 분무기는 해당 위치에서 십자가 모양으로 1씩 뺀다.

예를 들어 위의 맵에서 X와 Y에 분무기가 있다고 할 때, X는 {a, b, c, d, e, f, g, h, i, j, k, l, m, n}에 영향을 미치고, Y는 {A, B, c, C, D, E, F, G, H, I, J, k, K, L}에 영향을 미친다.

X가 비료액 분무기, Y가 제초제 분무기라고 한다면 문제에서 주어지면, 문제의 입력은 아래와 같이 주어지게 된다.

이렇게 맵이 주어지면 분무기의 위치와 상태를 파악해서 맵을 출력하면 되는 문제다.

 

여기서 우리가 알아야될 건 2가지이다.

1. 분무기의 위치

2. 분무기의 상태

 

일단 분무기 위치부터 구해보자.

임의의 위치 A, A와 다른 위치인 B 있다고 하자. 이때 A가 영향을 미치는 곳과 B가 영향을 미치는 곳은 항상 겹치게 된다. 이는 한 지점에서 십자가로 영향을 주기 때문에 임의의 두 위치를 선택하더라도 서로 영향을 미친 다는 것은 자명하다.

 

이때 두 지점은 아래와 같이 2개의 점 혹은 8개의 점이 서로 영향을 미친다.

2칸이 곂치는 상황

8칸 곂치는 상황

 

여기서 곂치는 칸들을 주목해 보자.

겹치는 칸들은 초기값에서 2번의 업데이트가 진행된다. +1 혹은 -1 이든 결국 2번의 업데이트로 초기값의 홀짝상태와 같은 상태를 가진다.  위 예시에서도 곂치는 부분은 초기값과 같은 홀짝 상태(+1 한번, -1 한번)를 가지게 된다.

한 위치에서 영향을 미치는 칸은 15칸인데 임의의 두 점이 만났을 때 개수가 2개 혹은 8개가 줄어든다. 즉 15에서 13 혹은 7개로 영향을 미치는 칸이 홀수개임을 알 수 있다.

 

2개뿐만 아니라 n개의 점에 대해서 생각해 볼 때, n번째 과 1 ~ n-1 번째 점과의 겹치는 점의 개수는 15 - 2*A - 8*B (A와 B는 정수)로 겹치지 않는 위치의 개수가 항상 홀수를 유지함을 보일 수 있다. +1 혹은 -1이 2번 이상 중첩되더라도 결국 홀수번인지 짝수번인지가 중요하므로 2번 이상의 중첩은 문제가 되지 않는다.

(이래도 잘 모르겠다면 여러 예제를 만들어서 확인해 보면 된다)

 

이를 누적합을 함께 이용한다면 분무기의 위치를 찾아낼 수 있다.

임의의 위치에 대해 십자가로 15개의 칸의 값을 모두 합했을 때, 그 값이 홀수라면 우리가 앞에서 증명한 분무기의 위치 조건에 해당되기 때문에 그 지점들을 분무기의 위치로 지정해 주면 된다.

 

이렇게 1번 조건을 해결을 했다.

이제 2번 조건을 해결해 보자.

 

분무기의 상태를 찾는 방법은 크게 2가지가 있다. 이 글에선 2가지 모두 설명하겠다.

 

1. 개수의 유한성을 이용한 방법

우리는 분무기의 총개수를 알고 있다. 분무기가 총 M개라고 한다면 이 M개는 비료액 분무기와 제초제 분무기 2가지로 이루어져 있다. 즉 비료액 분무기의 수를 A, 제초제 분무기를 B라고 둔다면, M = A+B 가 성립한다.

우리는 이 점을 이용할 것이다.

 

분무기 C의 위치를 (x, y)라고 한다면, 이 점을 기준으로 십자가 형태의 영향권에서 분무기를 수를 세준다. 분무기 수는 전처리를 통해 구하거나 범위가 작기 때문에 실시간으로 구해도 된다.

 

이때 우리는 가정을 둘 것이다.

 

"만약 C가 비료액 분무기라면?"

 

C 기준으로 십자가 형태의 영향권에 +1이 됐을 것이다. 그러면 C의 영향권에 있는 15개의 칸에 모두 1씩 더해줬으니 우리가 분무기의 위치를 알기 위해 사용했던 누적합 배열에서 C의 위치에 15를 빼주자.

이제 C의 위치에서 누적합 값은 초기값과 C를 제외한 M-1 개의 점 사이에서 일어난 영향들의 총합이 된다.

 

그리고 우리는 범위가 작다는 점을 이용해서 C의 영향권에 있는 분무기의 개수를 알 수 있다. 

C으 영향권에 있는 분무기는 C에 +8 혹은 -8의 영향을 줄 것이고, 영향권에 없는 분무기는 +2 혹은 -2의 영향을 줄 것이다.

 

영향권에 있는 분무기의 수를 A, 영향권에 없는 분무기의 수를 B라고 하고

C의 누적합에 영향을 미치는 정도를 식으로 나타내면,

 

+8 * (영향권에 있는 비료액 분무기) - 8 * (A - 영향권에 있는 비료액 분무기) + 2 * (영향권에 없는 비료액 분무기) - 2 * (B - 영향권에 있는 비료액 분무기) 

 

가 될 것이다.

이 값을 앞서 구한 '초기값과 C를 제외한 M-1 개의 점 사이에서 일어난 영향들의 총합'과 비교해서 만약 같은 조건이 있다면, C는 비료액 분무기가 되는 것이고, 그렇지 않다면 C는 제초제  분무기가 되는 것이다.

(어떠한 조합도 나올 수 없다면 C는 비료액 분무기가 아니게 되니 제초제 분무기가 되고, 그게 아니면 비료액 분무기라는 사실은 자명하다.)

 

이렇게 분무기의 위치에 대해서 하나하나 탐색해 주면서 비료액 분무기인지, 제초제 분무기인지 찾아서 출력해 주면 된다.

 

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m,K;
ll inp[10][10];
ll ps[10][10];
ll ans[10][10];
void ps_set(){
	for(int i=1;i<=8;i++){
		for(int j=1;j<=8;j++){
			ps[i][j]=0;
			for(int k=1;k<=8;k++){
				ps[i][j]+=inp[i][k]+inp[k][j];
			}
			ps[i][j]-=inp[i][j];
		}
	}
}
ll func(ll v, ll a,ll b){ // a : 2, b : 8
	for(int i=0;i<=a;i++){
		for(int j=0;j<=b;j++){
			if(2*i-2*(a-i)+8*j-8*(b-j)==v)return 1;
		}
	}
	return 0;
}
int main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	cout.tie(0);
	cin >> m;
	cin >> K;
	ll t=m%2;
	for(int i=1;i<=8;i++){
		for(int j=1;j<=8;j++){
			cin >> inp[i][j];
		}
	}
	ps_set();

	for(int i=1;i<=8;i++){
		for(int j=1;j<=8;j++){
			if(ps[i][j]%2!=t){
				ll a=0,b=0;
				for(int k=1;k<=8;k++){
					if(ps[i][k]%2!=t){
						b++;
					}
					if(ps[k][j]%2!=t){
						b++;
					}
				}
				b-=2;
				a=K-b-1;
				if(func(ps[i][j]-(m*15+15),a,b)){ // +
					ans[i][j]=2;
				}else{ // -
					ans[i][j]=1;
				}
			}else{
				ans[i][j]=0;
			}
		}
	}
	
	for(int i=1;i<=8;i++){
		for(int j=1;j<=8;j++){
			if(ans[i][j]==2){
				cout << "+ ";
			}else if(ans[i][j]==1){
				cout << "- ";
			}else{
				cout << ". ";
			}
		}
		cout << "\n";
	}
	//cout << "\n";



}

 

2. 한 가지를 제외시키는 방법

1번과 누적합을 구하는 것까지는 동일하지만 그다음부터 달라진다.

이 방법은 누적합 배열을 통해 분무기의 위치를 찾고 분무기의 영향권에 모두 1을 빼준다.

 

이럴 경우, 비료액 분무기의 경우 분무기가 없던 상태로 돌아갈 것이고, 제초제 분무기는 같은 위치에 한 번 더 -1을 한 배열이 만들어질 것이다.

이렇게 만들어진 배열에 대한 누적합을 다시 만든다.

 

앞서 우리는 두 분무기가 2개 혹은 8개가 영향을 미친다는 것을 알 수 있다. 즉 +2, -2, +8, -8 값을 말하는데, 새로 만든 누적합 배열에선 비료액 분무기는 사라져 있고, 제초제 분무기는 2배가 되어있는 것이다. 즉 +2, -2, +8, -8이 +4, -4, +16, -16가 된다. 

1번 방법에서 했던 거처럼 이 방법에서도 C 분무기가 비료액 분무기로 가정을 하였기 때문에, C 분무기가 비료액 분무기가 맞다면 누적합에 +4 * A - 4 * B + 16 * C - 16 * D (A, B, C, D는 정수) 이 더해지더라도 4의 배수가 나타나야 된다.

반대로 C가 제초제 분무기일 경우, 15 * 2 인 30이 추가로 빠진 상태 이기 때문에 4로 나눴을 때 2가 남게 된다. 

 

이렇게 분무기가 있는 위치에서 하나하나 계산해 출력해 주면 된다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m,K;
ll inp[10][10];
ll ps[10][10];
ll nps[10][10];
ll ans[10][10];
void ps_set(){
	for(int i=1;i<=8;i++){
		for(int j=1;j<=8;j++){
			ps[i][j]=0;
			for(int k=1;k<=8;k++){
				ps[i][j]+=inp[i][k]+inp[k][j];
			}
			ps[i][j]-=inp[i][j];
		}
	}
}
void nps_set(){
	for(int i=1;i<=8;i++){
		for(int j=1;j<=8;j++){
			nps[i][j]=0;
			for(int k=1;k<=8;k++){
				nps[i][j]+=inp[i][k]+inp[k][j];
			}
			nps[i][j]-=inp[i][j];
		}
	}
}
void upd(ll a, ll b){
	for(int k=1;k<=8;k++){
		inp[k][b]--;
		inp[a][k]--;
	}
	inp[a][b]++;
}

int main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	cout.tie(0);
	cin >> m;
	cin >> K;
	ll t=m%2;
	for(int i=1;i<=8;i++){
		for(int j=1;j<=8;j++){
			cin >> inp[i][j];
		}
	}
	ps_set();
	for(int i=1;i<=8;i++){
		for(int j=1;j<=8;j++){
			if(ps[i][j]%2!=t){
				upd(i,j);
			}
		}
	}
	nps_set();
	for(int i=1;i<=8;i++){
		for(int j=1;j<=8;j++){
			if(ps[i][j]%2!=t){
				if((m*15-nps[i][j])%4==0){
					cout << "+ ";
				}else{
					cout << "- ";
				}

			}else{
				cout << ". ";
			}
		}
		cout << "\n";
	}


}

 

이 문제는 초기값이 주어지는데, 이는 짝수일 때와 홀수 일 때 두 가지에 대해 제초제와 비료액 분무기를 가르는 조건문을 반대로 해주면 된다.