[백준/C,C++] 2448번: 별 찍기 - 11

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

2448번: 별 찍기 - 11

풀이

 

위 그림처럼 프렉탈 형태의 별을 찍어야 하는 문제입니다.

 

처음 해당 문제를 접하고 2가지 해결법이 생각났습니다.

 

2차원 bool 배열을 만들어 해당 좌표에 '*' 혹은 공백인지 판단하여 저장한 후

 

배열을 돌며 별을 찍어내는 방법과

 

좌표가 주어지면 해당 좌표에 찍어야 할 문자를 판단하여 바로 출력하는 방법입니다.

 

 

결과적으론 후자의 방법을 택하여 문제를 해결하게 되었습니다.

 

먼저 제가 생각한 방법은 이렇습니다.

 

좌표가 주어지고 해당 좌표가 현재 삼각형의 레벨(3, 6, 12, 24, 48, ...)에 속해있다고 가정한 후,

 

그 삼각형의 레벨에 찍혀야 할 '*' 나 공백의 위치와 비교한 뒤 아니라면

 

하위 레벨로 재귀 호출 하는 것입니다.

 

 

24가 입력되었을 때 첫 레벨의 삼각형에서 찍혀야 할 문자들은 위와 같습니다.

 

삼각형 왼쪽과 오른쪽의 양변에 해당하는 좌표라면 '*'를 찍어주면 되고,

 

범위 밖과 중앙 아래의 작은 삼각형에 속한다면 공백을 찍어주면 됩니다.

 

그 외의 부분은 더 하위 레벨로 재귀 호출해 주면 되는 것이죠.

 

해당 부분은 '?'로 찍어보았습니다.

 

 

24가 입력되었을 때 두 번째 레벨인 12 크기의 삼각형까지만 찍어보면 위와 같은 그림이 됩니다.

 

삼각형의 양쪽 변에 해당하는 위치는 어떻게 구할 수 있을까요?

 

삼각형 제일 상단의 y좌표와 현재 입력된 y좌표의 차이를 생각해보면 됩니다.

 

삼각형 상단 부분의 y좌표가 0이고 중앙 부분의 x좌표가 23이라면,

 

y좌표가 1일 때, 삼각형의 양변 위치의 x좌표는 22와 24가 됩니다.

 

 

상단 부분과 하단 부분을 구하는 것은 어렵지 않습니다.

 

상단 부분은 y좌표가 주어졌을 때 현재 레벨의 크기로 나눈 후 곱해주면 됩니다.

 

하단 부분은 상단 부분에서 현재 레벨의 크기만큼 더하고 1을 빼주면 됩니다.

 

 

#include <iostream>

using namespace std;

void star(int i, int j, int num, int mid)
{
	// 제일 상단 부분과 하단 부분
	int top = i / num * num, bot = top + num - 1;
	// 상단으로부터의 거리, 하단으로부터의 거리
	int dis = abs(top - i), rdis = abs(bot - i);
	// 왼쪽 끝과 오른쪽 끝 (상단 부분부터 늘어남)
	int left = mid - dis, right = mid + dis;
	// 왼쪽 끝과 오른쪽 끝 (상단 부분부터 줄어듦)
	int rleft = mid - rdis, rright = mid + rdis;
	if (num == 3) {
		rleft++; rright--;
	}

	// 삼각형의 양변 밖에 있다면 공백
	if (j < left || j > right) cout << ' ';
	// 삼각형 안의 중앙 아래 삼각형
	else if (dis >= num / 2 && j >= rleft && j <= rright) cout << ' ';
	// 삼각형의 양변
	else if (j == left || j == right) cout << '*';
	else {
		// 제일 작은 삼각형의 하단
		if (num == 3) cout << '*';
		else {
			// 중앙값을 갱신하고 재귀 호출
			if (dis >= num / 2 && j < mid) mid -= (num / 2);
			else if (dis >= num / 2 && j > mid) mid += (num / 2);
			star(i, j, num / 2, mid);
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N; cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N * 2 - 1; j++) {
			star(i, j, N, (N * 2 - 1) / 2);
		}
		cout << '\n';
	}

	return 0;
}