백준 1074번 : Z

문제 링크 : www.acmicpc.net/problem/1074

풀이에 참고한 링크 : www.acmicpc.net/board/view/46542

내 풀이 (2020.12.17.) :

#include <iostream>
#include <cmath>

using namespace std;

int N, R, C;
int cnt = 0;

void search(int N, int r, int c) {
	if (N == 0) {
		if(R == r && C == c){
			cout << cnt;
		}
		cnt++;
		return;
	}

	int n = pow(2, N - 1);
	search(N - 1, r, c);
	search(N - 1, r, c + n);
	search(N - 1, r + n, c);
	search(N - 1, r + n, c + n);
}

int main() {
	cin >> N >> R >> C;
	search(N, 0, 0);
}

결과 : 시간 초과

  이 풀이의 시간복잡도는 O(2^2N)인데 N이 최대 15이므로

  최대 걸리는 시간은 2^30 = 10,0000,0000 (10초) 이다.

---

내 풀이2 (2020.12.17.) :

#include <iostream>
#include <cmath>

using namespace std;

int N, R, C;
int cnt = 0;

void search(int N, int r, int c) {
	if (N == 0) {
		if(R == r && C == c){
			cout << cnt;
		}
		return;
	}

	int n = pow(2, N - 1);
	int nn = pow(4, N - 1);

	if ((R < r + n) && (C < c + n)) {
		cnt += nn * 0;
		search(N - 1, r, c);
	}
	else if ((R < r + n) && (C >= c + n)) {
		cnt += nn * 1;
		search(N - 1, r, c + n);
	}
	else if ((R >= r + n) && (C < c + n)) {
		cnt += nn * 2;
		search(N - 1, r + n, c);
	}
	else if ((R >= r + n) && (C >= c + n)) {
		cnt += nn * 3;
		search(N - 1, r + n, c + n);
	}
}

int main() {
	cin >> N >> R >> C;
	search(N, 0, 0);
}

 

결과 : 제한 시간 내 성공

  r, c를 확인하면서 4개 자식 노드들 중 1개만을 탐색하되

  nn을 통해 cnt를 자동으로 카운트 해주었다.

  이 풀이의 시간복잡도는 O(N) 밖에 되지 않는다.