[분할 정복] Z 1074 ○

문제 해설 및 주의사항

1. 종이의 개수 문제 와 유사하다.

---

 

풀이

1. N 이 최대 15이다.

 

2. 문제를 분할하자

 

a. 현재 정사각형을 4등분한다.

b. 2x2 정사각형이 되면, z 모양으로 순회한다.

c. r, c 에 방문하면 순회를 마친다.

 

3. flag 전역변수

- r, c 를 만나면 flag 를 false 로 바꾸어서 이후의 재귀함수가 작동하지 않게 한다.

 

4. 재귀 함수의 시간을 줄이는 조건 추가하기

- r, c 가 현재 정사각형에 들어있지 않다면, ret 에 정사각형의 크기만큼을 더해주고 끝낸다.

---

풀이코드 (시간 초과)

#include <iostream>

using namespace std;
const int MAX = 100000;

int n, r, c;

/*

a. 현재 정사각형을 4등분한다.

b. 2x2 정사각형이 되면, z 모양으로 순회한다.

c. r, c 에 방문하면 순회를 마친다.

*/

bool flag = true;
int solve(int y, int x, int width){
	// c.
	if(y == r && x == c) {
		flag = false;
		return 0;
	}
	if(width == 1) {
		return 1;
	}
	
	int ret = 0;

	if(flag)
		ret += solve(y, x, width / 2);
	if(flag)
		ret += solve(y, x+width/2, width/2);
	if(flag)
		ret += solve(y+width/2, x, width/2);
	if(flag)
		ret += solve(y+width/2, x+width/2, width/2);
	
	return ret;
}

int main(){
	cin >> n >> r >> c;
	
	cout << solve(0,0,1 << n) << endl;
}

풀이코드 (정답)

#include <iostream>

using namespace std;
const int MAX = 100000;

int n, r, c;

/*

a. 현재 정사각형을 4등분한다.

b. 2x2 정사각형이 되면, z 모양으로 순회한다.

c. r, c 에 방문하면 순회를 마친다.

*/

bool flag = true;
int solve(int y, int x, int width){
	// c.
	if(y == r && x == c) {
		flag = false;
		return 0;
	}
	if(width == 1) {
		return 1;
	}
	
	int ret = 0;

	if( r < y + width && r >= y && c < x + width && c >= x){
		if(flag)
			ret += solve(y, x, width / 2);
		if(flag)
			ret += solve(y, x+width/2, width/2);
		if(flag)
			ret += solve(y+width/2, x, width/2);
		if(flag)
			ret += solve(y+width/2, x+width/2, width/2);
	}
	else{
		ret += width * width;
	}
	
	return ret;
}

int main(){
	cin >> n >> r >> c;
	
	cout << solve(0,0,1 << n) << endl;
}

 

---

퇴고

1. 시간 초과

- 시간을 줄이는 조건 을 어떻게 생각해낼 수 있을것인가