[C++] 백준 1074번 : Z

 

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

1074번: Z

분할정복 문제이다.

그치만 이 문제에서 모든 곳을 다 돌아다니며 원하는 결과를 얻어내려고 한다면, 시간초과가 난다.

#include <iostream>
#include <stack>
#include <vector>
#include <cmath>

#include<algorithm>


using namespace std;

int r,c;
int** board;
int turn = 0;
int dynamicX[4] = {0, 0, 1, 1};
int dynamicY[4] = {0, 1, 0, 1};
bool flag = true;


void draw(int x, int y) {
	
	// draw Z
	for (int i = 0; i < 4; i++) {
		board[x + dynamicX[i]][y + dynamicY[i]] = turn++;
	}
}

void divideDraw(int n, int x, int y) {

	if (x == r && y == c) {

		flag = false;
		printf("%d",turn);

	}
	
	if ( pow(x%2,n) == 0 && pow(y%2,n) == 0 && flag) {
		turn--;
		// draw Z
		for (int i = 0; i < 4 && flag; i++) {
//			board[x + dynamicX[i]][y + dynamicY[i]] = turn++;
			
			if (n > 0) {
				turn++;
				int currX = x + pow(2,n-1) * dynamicX[i];
				int currY = y + pow(2,n-1) * dynamicY[i];

				divideDraw(n-1, currX, currY);
			}

		}
	} 

	
	

}


int main() {
	int n ;
	cin >> n >> r >> c;
		

	
	divideDraw(n,0,0);
	
	
	
	return 0;
}

 

위의 코드가 모든 방을 다 돌아다니는 거다.

하루죙일고민해서짰는데 시간초과나서 진짜 노트북을 박살내고싶었따ㅠㅠㅠㅠㅠㅠ

멍청한 내탓이지 뭐..

 

#include <iostream>
#include <stack>
#include <vector>
#include <cmath>

#include<algorithm>


using namespace std;

int r,c;
//int** board;
int loc = 0;
//int dynamicX[4] = {0, 0, 1, 1};
//int dynamicY[4] = {0, 1, 0, 1};
//bool flag = true;




void findZLoc(int n, int x, int y) {
	if (n > 0) {
		int currPoint = pow(2, n-1);
		int areaX = x >= currPoint ? 1 : 0;
		int areaY = y >= currPoint ? 1 : 0;
		int area = areaX*2 + areaY;
		loc += (currPoint * currPoint) * area;
		findZLoc(n-1, x % currPoint, y % currPoint);
	} else {
		cout << loc;
	}
}


int main() {
	int n ;
	cin >> n >> r >> c;

	
	findZLoc(n,r,c);
	
	
	
	return 0;
}

 

알고 겁나 잘하는 지인에게 힌트를 받고 내 잘못된 점을 반성해서 다시짰다.

생각보다 금방 짰다.

아이디어는 전체를 4공간으로 자르고, 찾으려는 방이 4구역 중 어디있는지 고려하는 방식으로 쭉쭉쭉 분할 정복해나가는 것이다.

1~4구역중 한 곳을 찾으면, 그 까지 나올 수 있는 차례를 단순 덧셈해주는 식으로 구했다.