[BOJ]1074 - Z

1074

최종 코드

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

long cnt{ 0 };
long n, r, c;

void zcount(long size, long row, long col) {

	if (row == r && col == c)
	{
		cout << cnt;
		return;
	}

	if (r < row + size && r >= row && c < col + size && c >= col)
	{
		zcount(size/2, row, col);
		zcount(size/2, row, col + size/2);
		zcount(size/2, row + size/2, col);
		zcount(size/2, row + size/2, col + size/2);
	}
	else
	{
		cnt += size*size;
	}
}


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

	zcount(1 << n, 0, 0);


}

구글링으로 답을 찾아봤는데 갑을 저장하지 않고 r과 c를 사분면에서 찾아 값을 도출하는 방식이었다.

굳이 값을 저장하지 않아도 해결 가능!

시간 정해놓고 푸는 게 좋을 것 같다.

시행 착오

#include <iostream>
#include <vector>
using namespace std;

long cnt{ 0 };
vector <vector <int>> arr;


void zcount(int n, int row, int col)
{
	if (n == 0)
	{
		arr[row][col] = cnt;
		cnt++;
		return;
	}
	else
	{
		zcount(n - 1, row, col);
		zcount(n - 1, row, col + (1 << (n-1)));
		zcount(n - 1, row + (1 << (n - 1)),col);
		zcount(n - 1, row + (1 << (n - 1)), col + (1 << (n - 1)));
		return;
	}
}

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

	for (int i = 0; i < (1 << n); i++)
	{
		vector <int> v(1 << n);
		arr.push_back(v);
	}

	zcount(n, 0, 0);

	cout << arr[r][c];
}

이렇게 짜니까 메모리 초과가 왔다.

참고자료

---

1074 c++ 솔루션