[백준] 1074 Z / 분할정복 (C++)

문제 링크

처음에 이렇게 푸니까 시간 초과가 났다.

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

int N, r, c;
int cnt = 0;

void DFS(int x1, int y1, int x2, int y2)
{
	int width = x2 - x1 + 1;
	int height = y2 - y1 + 1;

	if (width == 2 && height == 2)
	{
		for (int i = y1; i <= y2; i++)
		{
			for (int j = x1; j <= x2; j++)
			{
				if (i == r && j == c)
				{
					cout << cnt;
					return;
				}
				cnt++;
			}
		}
		return;
	}
	else
	{
		int midX = (x2 + x1) / 2;
		int midY = (y1 + y2) / 2;

		DFS(x1, y1, midX, midY);
		DFS(midX + 1, y1, x2, midY);
		DFS(x1, midY + 1, midX, y2);
		DFS(midX + 1, midY + 1, x2, y2);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> r >> c;

	int x = pow(2, N);
	DFS(0, 0, x - 1, x - 1);

	return 0;
}

그래서 해당 행,열 값이 없는 곳은 개수만 더해주고 넘어가는 방식으로 바꾸었다.

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

int N, r, c;
int cnt = 0;

void DFS(int x, int y, int width)
{
	if (x == r && y == c)
	{
		cout << cnt;
		return;
	}

	// 그 위치 안에 있으면
	if (r < x + width && r >= x && c >= y && c < y + width) 
	{
		// 좌상
		DFS(x, y, width/2);
		// 우상
		DFS(x, y + width/2, width/2);
		// 좌하 
		DFS(x + width/2, y, width/2);
		// 우하
		DFS(x + width/2, y + width/2, width/2);
	}
	else	
	{
		// 더 볼 필요 없으니 그냥 센다.
		cnt += width * width;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> r >> c;

	int x = pow(2, N);
	DFS(0, 0, x);

	return 0;
}