BOJ 1780 - 종이의 개수

• 3^n x 3^n으로 이루어진 행렬이 주어지는데, 이 행렬을 9분할하면서 분할된 조각의 모든 원소같으면 그 조각은 분할을 멈춘다. 분할이 모두 종료된 후 원소의 종류별(-1/0/1) 조각의 개수를 구하는 문제이다.

문제 풀이

• Merge sort와 마찬가지로 1x1까지 분할한 후 합쳐가며 처리했다. 아래 code #2은 풀고난 후 다른 사람들의 풀이를 참고해서 개선한 코드이다. 개선한 점은 밑에서 설명하겠다.

소스코드

//code #1
#include<bits/stdc++.h>
using namespace std;

int d(int ai, int aj, int bi, int bj);

int n, p[2188][2188], ncnt[3];

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>p[i][j];
	int res=d(1, 1, n, n);
	if(res!=2) ncnt[res+1]++;
	cout<<ncnt[0]<<"\n"<<ncnt[1]<<"\n"<<ncnt[2];
}

int d(int ai, int aj, int bi, int bj){
	int c[4]={0, 0, 0, 0};
	if(bi-ai<2) return p[ai][aj];

	int ridx=0, dif=(bi-ai+1)/3, res[9];
	for(int i=0;i<3;i++) for(int j=0;j<3;j++)
		c[d(ai+i*dif, aj+j*dif, ai+(i+1)*dif, aj+(j+1)*dif)+1]++;
	for(int i=0;i<3;i++) if(c[i]==9) return i-1;
	ncnt[0]+=c[0];
	ncnt[1]+=c[1];
	ncnt[2]+=c[2];
	return 2;
}

//code #2
#include<bits/stdc++.h>
using namespace std;

int n, p[2188][2188], ncnt[3];

void d(int ai, int aj, int bi, int bj){
	if(bi==ai){
		ncnt[p[ai][aj]+1]++;
		return;
	}
	int t=p[ai][aj], dif=(bi-ai+1)/3;
	for(int i=ai;i<=bi;i++){
		for(int j=aj;j<=bj;j++){
			if(p[i][j]!=t){
				t=p[i][j];
				for(int k=0;k<3;k++) for(int l=0;l<3;l++)
					d(ai+k*dif, aj+l*dif, ai+(k+1)*dif-1, aj+(l+1)*dif-1);
				break;
			}
		}
		if(t!=p[ai][aj]) break;
	}
	if(t==p[ai][aj]) ncnt[t+1]++;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>p[i][j];
	d(1, 1, n, n);
	cout<<ncnt[0]<<"\n"<<ncnt[1]<<"\n"<<ncnt[2];
}

풀고나서

• 시간이 1000ms가 넘게 나오길래 다른 사람들의 코드를 읽어보았다. 실행시간은 평균적으로 300~400ms였고 나랑 다른점은 모든 1x1 종이를 보지 않고 현재 조각을 확인하다가 다른 원소가 나오면 그때 분할을 시작하는 점이었다. 이때문에 시간차이가 나는줄알고 저 방법대로 해봤는데 시간이 그대로렸고 알고보니 sync_with_stdio를 안했었다. code #1도 저걸 안했었고, 하니까 300ms대로 나왔다.
  하지만 불필요한 처리를 하지 생략한다는 점에서 code #2가 더 좋은 것 같긴 하다.