[BAEKJOON 1074번] (C++) Z

 

www.acmicpc.net/problem/1074

1074번: Z

 

문제 해결

• 이전에 해결하였던 쿼드트리 문제와 동일하게 각각의 problem을 4개의 subProblem으로 나누어 해결하였다.
• 하지만 이 문제는 최대 2의 15승까지의 입력 값을 받기 때문에 크기 1의 subProblem를 모두 찾아서 위치를 비교하여 문제를 해결할 경우 시간초과가 난다.
• 그렇기 때문에 subProblem으로 들어왔을 때 만약 주어진 (r,c)가 현재 subProblem의 범위에 포함되어 있지 않은 경우에는 현재 subProblem에 포함되어 있는 개수 h* h를 출력값 answer에 더해주고 return 시켜서 더이상 현재 subProblem이 분할하여 재귀에 들어가지 않도록 하였다.
• 문제 해결순서는 현재 문제에서 주어진 Z 와 같은 이동 순서를 가지므로 최종 출력값이 마지막에 문제에 대한 답을 찾기 전까지의 모든 최하위 subProblem의 갯수와 동일하므로 문제가 발생하지 않는다.
• 최종적으로 주어진 c와 r에 해당하는 subProblem에서 현재 answer값의 출력하고 return하여 이후 과정에서 출력 값이 변화하는 것에 대한 문제를 해결하였다.

 

코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int> check;
int N, r, c;
int answer = 0;

void solution(int h, int x, int y)
{
	//입력값으로 주어진 r과 c에 해당하는 subProblem에서 출력
	if (x == r && y == c){
		cout << answer << endl;
		return;
	}
	//c와 r이 현재 subProblem의 범위 내에 포함되지 않는 경우
	//현재 subProblem의 크기만큼 answer에 더해주고 return하여
	//더이상 재귀를 진행하지 않는다.
	if (r > x + h - 1 || c > y + h - 1 || r < x || c < y){
		answer += h * h;
		return;
	}

	solution(h / 2, x, y);
	solution(h / 2, x, y + (h / 2));
	solution(h / 2, x + (h / 2), y);
	solution(h / 2, x + (h / 2), y + (h / 2));
}

int main() {

	cin >> N >> r >> c;
	solution(pow(2, N), 0, 0);
	return 0;
}

 

 

결과