백준 10993번 별 찍기 - 18

문제 링크입니다: https://www.acmicpc.net/problem/10993

10993번: 별 찍기 - 18

재귀함수를 작성해야하는 별 찍기 문제였습니다.

다른 별 찍기 문제보다 난이도가 있기 때문에 직접 가로와 세로 길이를 세어가면서 규칙을 찾아야하는 문제였습니다.

직접 세어본다면 주어진 N에 대해 제일 긴 가로 길이는 2^(N + 1) - 3이고 높이는 2^N - 1 이라는 것을 알 수 있습니다.

거기서부터 시작하여 N에서부터 1까지 각 단계(깊이?)마다 어떤 규칙이 있는지 찾아내면 되는데,

단계 혹은 깊이가 홀수일 때와 짝수일 때 서로 다른 규칙을 갖는다는 것을 알 수 있습니다.

코드에서는 재귀 함수 단계(깊이?)를 height라고 작성했지만 사실 height 보다는 level 혹은 depth 가 더 어울리는 매개변수명인 것 같습니다.

(주의: 출력을 할 때 오른쪽에는 공백을 출력하면 안됩니다. 공백을 출력할 경우 WA 받습니다.)

 

	#include <iostream>
	#include <cmath>
	using namespace std;
	const int MAX = 1024;
	char starGraph[MAX][2 * MAX];
	void func(int y, int x, int height)
	{
	if (height == 1)
	{
	starGraph[y][x] = '*';
	return;
	}
	int row = pow(2, height + 1) - 3;
	int col = pow(2, height) - 1;
	if (height % 2)
	{
	for (int i = 0; i < row; i++)
	{
	starGraph[y + col - 1][x + i] = '*';
	}
	for (int i = 0; i < col - 1; i++)
	{
	starGraph[y + i][x + row / 2 - i] = '*';
	starGraph[y + i][x + row / 2 + i] = '*';
	}
	func(y + col / 2, x + pow(2, height - 1), height - 1);
	return;
	}
	for (int i = 0; i < row; i++)
	{
	starGraph[y][x + i] = '*';
	}
	for (int i = 1; i < col; i++)
	{
	starGraph[y + i][x + i] = '*';
	starGraph[y + i][x + row - (i + 1)] = '*';
	}
	func(y + 1, x + pow(2, height - 1), height - 1);
	return;
	}
	int main(void)
	{
	int N;
	cin >> N;
	func(0, 0, N);
	int row = pow(2, N + 1) - 3;
	int col = pow(2, N) - 1;
	for (int i = 0; i < col; i++)
	{
	if (N % 2)
	{
	for (int j = 0; j < row - col + (i + 1); j++)
	{
	char c = starGraph[i][j] == '*' ? '*' : ' ';
	cout << c;
	}
	cout << "\n";
	continue;
	}
	for (int j = 0; j < row - i; j++)
	{
	char c = starGraph[i][j] == '*' ? '*' : ' ';
	cout << c;
	}
	cout << "\n";
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~