BaekJoon 1074번: Z

풀이법

1) N의 크기가 크지 않기에 재귀함수로 풀 수 있는 대표적인 문제이다.

2) 분할과 재귀함수를 통해 시간 제한인 0.5초 이내에 값을 도출할 수 있었다.

#include <iostream>
#include<math.h>
using namespace std;
int n,r,c;
int arr[2][2] = { {3,2},{1,0} };
void z(int r, int c,int n, long long max)
{
	if (n == 1)
	{
		cout << max-arr[r][c];
		return;
	}
	int a = (int)pow(2, n);
	
	if (r < a / 2 && c < a / 2)
	{
		max = max- (int)pow(4, n - 1)*3;
		z(r, c, n - 1,max);
	}
	else if (r < a / 2 && c >= a / 2)
	{
		max = max - (int)pow(4, n - 1)*2;
		z(r, c-a / 2, n - 1,max);
	}
	else if (r >= a / 2 && c < a/2)
	{
		max = max - (int)pow(4, n - 1);
		z(r-a / 2, c, n - 1,max);
	}
	else
	{
		z(r-a / 2, c-a / 2, n - 1,max);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> r >> c;
	long long a = int(pow(2,n))*int(pow(2,n))-1;

	z(r, c, n,a); // 1 1
	
}

한계점 및 개선사항 (+주의사항)

규칙을 찾는 것이 중요하다. 규칙을 발견한다면 어렵지 않게 코딩할 수 있는 문제이다.

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest