[Baekjoon] 1074번: Z

🥅 문제

https://www.acmicpc.net/problem/1074

 

🔍 설계

2 X 2가 될 때까지 나누다가 2 X 2가 되었을 때, Z를 그리면서 순서를 센다.

 

나누는 과정에서도 Z 모양으로 나눈다.

 

중요한 것은 영역을 나누는 과정에서 Target 칸이 속하지 않은 영역의 칸 수는 순서를 신경쓰지 않아도 되므로, 쉽게 구할 수 있다는 것이다.

 

재귀 함수를 통해  영역의 한 변의 길이가 2라면, Z를 그리면서 순서를 센다. 2보다 크다면 Target 칸이 속하지 않은 영역의 칸 수를 더한다.

 

주의해야할 점은 나누는 과정에서도 Z 모양으로 나누기 때문에 순서를 신경써야 한다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;	
int n, r, c, result = 0;

void Z(int cur_length, int start_x, int start_y){
	if (cur_length == 2){
		if (start_x == r && start_y == c){
			return;
		}
		result += 1;
		if (start_x == r && start_y + 1 == c){
			return;
		}
		result += 1;
		if (start_x + 1  == r && start_y== c){
			return;
		}
		result += 1;
		if (start_x + 1 == r && start_y + 1 == c){
			return;
		}
	}
	else{
		int half_x = start_x + cur_length/2;
		int half_y = start_y + cur_length/2;
		int out_x = start_x + cur_length;
		int out_y = start_y + cur_length;
		if (start_x <= r && r < half_x && start_y <= c && c < half_y){
			Z(cur_length/2, start_x, start_y);
			return;
		}
		result += (cur_length/2)*(cur_length/2);
		if (start_x <= r && r < half_x && half_y <= c && c < out_y){
			Z(cur_length/2, start_x, half_y);
			return;
		}
		result += (cur_length/2)*(cur_length/2);
		if (half_x <= r && r < out_x  && start_y <= c && c < half_y){
			Z(cur_length/2, half_x, start_y);
			return;
		}
		result += (cur_length/2)*(cur_length/2);
		if (half_x <= r && r < out_x && half_y <= c && c < out_y){
			Z(cur_length/2, half_x, half_y);
			return;
		}
	}
} 

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n >> r >> c;
	Z(pow(2, n), 0, 0);
	cout << result << "\n";
	return 0;
}

 

📝 메모

내가 이용할 수 있는 것이 무엇인지 인지하고, 큰 문제를 간단하게 해결할 수 있는 방법에 대해 고민하는 것이 필요했다.