[알고리즘] Z

구현 방식

• 3년전에 풀다가 시간초과떠서 성공하지 못한 문제를 다시 도전해서 풀어보았다. 그래도 3년전보다 성장한것같아 뿌듯..

• 그때의 방법은 몇번째인지 탐색하는 카운터를 만들어 분할 정복을 빠짐없이 거쳐서 완성해야하는 방식이었다.
• 이렇게 되면 최대 2 ^ 15 * 2 ^ 15 로 1 억을 넘게 되어 0.5초만에 풀 수 없었다.
• 그래서 두가지 기능을 추가했다.
  • 현재 탐색하고 있는 영역의 시작 idx 를 기록
  • 현재 영역에 입력값에서 원하는 r,c 값이 포함이 안되면 탐색 X
• 현재 탐색하고 있는 영역의 시작 idx는 사진과 같은 규칙에의해 아래와 같이 나타낼 수 있다.

startidx = [이전 startidx] + (현재 영역 길이 / 2 ) ^ 2

코드

• 최종 코드는 아래와 같다.

int result, r, c;

void solution(int N)
{
	divide({ 0,0 }, pow(2,N), 0);
	cout << result;
}


void divide(pair<int,int> start, int size, int startIdx)
{
	if (start.first == r && start.second == c)
	{
		result = startIdx;
		return;
	}

	else
	{
		pair<int, int> next[] = { start, {start.first , start.second + size / 2}, {start.first + size / 2, start.second }, {start.first + size / 2, start.second + size / 2 } };
		for(int i = 0; i < 4; i++)
		{
			// r, c 가 속한 부분만 탐색
			if(next[i].first <= r && r < next[i].first + size / 2 && next[i].second <= c && c < next[i].second + size /2 )
				divide(next[i], size / 2, i * pow((size / 2), 2) + startIdx);
		}
	}
}