1074번: Z

Memo

로직 설명

• 재귀적으로 함수를 구현했습니다. 인자로 넘어온 현재 길이를 토대로 4분면을 만들고, (r,c) 의 위치를 수식을 통해 어느 사분면에 위치한지 찾습니다.
• 해당 사분면으로 들어갈 수 있도록, 조건문을 적절히 걸어줍니다.

⇒ 일반적인 divide and conquer 방식으로 코드를 작성하면 시간초과가 발생합니다. 이는 시간복잡도가 2^15 * 2^15 정도 나오게 되는데, 이는 약 10억 정도가 되므로 제한 시간안에 답을 구해낼 수는 없습니다.

• 시간 초과 발생 코드

Code

제출 날짜

2021/04/27

메모리

2200 KB

시간

0 ms

#include <iostream>
#include <cmath>

int N, r, c;
int cnt;

void io_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	io_faster();
	std::cin >> N >> r >> c;
}

void dc(int y, int x, int len)
{
	if (y == r && x == c)
		return;
	if (y <= r && r < y + len/2 && x <= c && c < x + len / 2)
		dc(y, x, len / 2);
	else if (y <= r && r < y + len / 2 && x + len / 2 <= c && c < x + len)
	{
		cnt += (std::pow(len / 2, 2));
		dc(y, x + len / 2, len / 2);
	}
	else if (y + len / 2 <= r && r < y + len && x <= c && c < x + len / 2)
	{
		cnt += 2 * (std::pow(len / 2, 2));
		dc(y + len / 2, x , len / 2);
	}
	else
	{
		cnt += 3 * (std::pow(len / 2, 2));
		dc(y + len / 2, x + len / 2, len / 2);
	}
}

void solve()
{
	dc(0, 0, std::pow(2, N));
}

void print_val()
{
	std::cout << cnt;
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}