백준 1074 _ Z

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

1074번: Z

---

✨ 내 소스 코드

#include<iostream>

using namespace std;
int Route[][2] = { {0,0}, {0,1}, {1,0}, {1,1} };
int r, c;
int result = 0;

bool z(int x, int y, long long int N) {
	if (N > 2) {
		if (z(x, y, N / 2)) {
			return true;
		}
		else if (z(x, y + (N / 2), N / 2)) {
			return true;
		}
		else if (z(x + (N / 2), y, N / 2)) {
			return true;
		}
		else if (z(x + (N / 2), y + (N / 2), N / 2)) {
			return true;
		}
	}
	else {
		for (int i = 0; i < 4; i++) {
			if (x + Route[i][0] == r && y + Route[i][1] == c) {
				return true;
			}
			else {
				result +=1;
			}
		}
		return false;
	}
	return false;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	long long int N;
	cin >> N >> r >> c;
	z(0, 0, (1 << N));
	cout << result;

	return 0;
}

 

🙏 문제 풀이

제곱 계산을 하는걸 단순화 하기 위해서 '1<<N' 으로 계산하였다

 

N이 2보다 크면 아직 4등분을 더 할 수 있다는 것이기에, 4등분을 해서 재귀를 진행
(r, c)가 x, y보다 크면 해당 분면 재귀를 진행하지 않고 그만큼의 수를 더해버리면 시간을 더 단축 시킬 수 있을 것 같다! 이 부분 수정! 

 

Route[][]는 Z모양으로 이동을 해야되기에, 이동 좌표 경로를 미리 저장

 

 

⭐ 문제 풀이 결과