백준 2447 별찍기10

별찍기10 (백준 2447)

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

정말 오랜만에 보는 분할정복 문제이다
사실 코딩 테스트 문제를 푸는 것도 굉장히 오랜만이고
별찍기 정도는 금방 풀 수 있을것 같았다

쿼드트리랑 비슷한 방식으로 풀면 되겠지 싶었는데…
‘줄바꿈’을 고려하지 못하고 이상한 방식으로 재귀를 짰던 것 같다

블로그를 보았는데도 이해가 되지 않아 한창 손으로 그림을 그리다
겨우 이해하였다

Code

#include<iostream>
#include<string>
#include<vector>

using namespace std;

/*
	줄바꿈이 중요하기에
	'처음'부터 끝까지 찍어야 함

	i좌표와 j좌표를 기준으로
	판단한다

	중간 부분을 판단하는 것은
	3x3의 중간 부분이므로
	0,0 1,0 2,0
	1,0 1,1 2,1
	2,0 2,1 2,2
	
	1,1 이 공백이 되어야 하므로
	i%3 == 1 && j % 3 == 1

	또한 추가적으로
	9 이상의 경우는
	'가운데 부분이' 통째로 비워져야 하므로

	0,0 1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0
	0,1 1,1 2,1 3,1 4,1 5,1 6,1 7,1 8,1
	0,2 1,2 2,2 3,2 4,2 5,2 6,2 7,2 8,2
	0,3 1,3 2,3 3,3 4,3 5,3 6,3 7,3 8,3
	0,4 1,4 2,4 3,4 4,4 5,4 6,4 7,4 8,4
	0,5 1,5 2,5 3,5 4,5 5,5 6,5 7,5 8,5
	0,6 1,6 2,6 3,6 4,6 5,6 6,6 7,6 8,6
	0,7 1,7 2,7 3,7 4,7 5,7 6,7 7,7 8,7
	0,8 1,8 2,8 3,8 4,8 5,8 6,8 7,8 8,8

	이 중 
	3,3 ~ 5,3,
	3,4 ~ 5,4,
	3,5 ~ 5,5
	부분이 공백이여야 함
	이 때,
	이것은 9분할 된 '위치' 이므로
	
	(i/3)인 3 ,4 ,5 번째 인덱스가
	1이 되며,
	이후 (i/3)%3 == 1 을 통해 해당 위치를 특정할 수 있음!

	따라서 
	(i / 3) % 3 == 1 && (j/3) % 3 == 1
	을 만족하는 좌표를 특정할 수 있다

	입력이 반드시 3의 배수이기에 저 나누는 3 부분을
	(i / n) % 3 == 1 && (j/n) % 3 == 1
	로 공식화 하여 ' ' 으로 표기하면 된다

	n이 3인 경우는 3x3 박스이고,
	'중앙'이 아닌 경우는 별을 찍어준다
	
	그 외의 경우 판별 함수를 재귀하여
	재 판별한다
*/
bool isStarPrint(int i, int j, int n)
{
	if ((i / n) % 3 == 1 && (j / n) % 3 == 1)
	{
		return false;
	}

	if (n / 3 == 0)
	{
		return true;
	}

	return isStarPrint(i, j, n / 3);
}

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

	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (isStarPrint(i,j,n) == true)
			{
				cout << '*';
			}
			else
			{
				cout << ' ';
			}
		}
		cout << '\n';
	}


	return 0;
}

해결 아이디어

1. ‘중앙’ 부분을 판별하여 ‘일렬’로 출력하는 것이 이번 문제의 핵심
   
2. 현재 시점의 좌표가
   ‘중앙’에 해당하는지를 파악하는 공식은
   (i / n) % 3 == 1 && (j/n) % 3 == 1 이다
   (세부 설명은 문제 주석 참고)
   그렇기에 이 공식에 해당한다면
   ‘중앙’의 부분이므로 ‘공백’을 출력
   
3. 해당 부분이 3x3의 ‘나머지’ 부분이라면 ‘별’을 출력하고
   그렇지 않다면 다시 판별 함수의 재귀를 돌려준다
   
4. 하나의 위치값 마다 해당 함수를 돌려주면 문제는 해결