[백준 16505] 별

www.acmicpc.net/problem/16505

16505번: 별

재귀를 사용하는 문제이다.

규칙을 찾아보면 

0에서 *

1에서 * *

        *

 

2에서 f(1) f(1)

        f(1)

임을 알 수 있다. 그냥 printf를 써버리면 저런 모양이 안나오고 배열을 사용해야 한다.

 

재귀함수를 호출할 때마다 별찍기를 시작할 (row, col)을 정해서 별을 찍도록 한다.

row와 col은 제곱수만큼 늘어나므로 기저 조건 (0,0)에 2의 제곱수만큼 더한 시점이 n-1번째 별찍기를 시작하는 시점일 것이다. 

#include <stdio.h>
#include <cmath>

using namespace std;

char board[1024][1024];

void Print(int n)
{
  int m = pow(2, n);
  for (int i = 0; i < m; i++)
  {
    for (int j = 0; j < m - i; j++)
    {
      printf("%c", board[i][j]);
    }
    printf("\n");
  }
}
void fillStar(int cnt, int row, int col)
{
  if (cnt == 0)
  {
    board[row][col] = '*';
    return;
  }

  fillStar(cnt - 1, row, col);
  fillStar(cnt - 1, row + pow(2, cnt - 1), col);
  fillStar(cnt - 1, row, col + pow(2, cnt - 1));
}

int main(void)
{
  int n;
  scanf("%d", &n);

  for (int i = 0; i < pow(2, n); i++)
  {
    for (int j = 0; j < pow(2, n); j++)
    {
      board[i][j] = ' ';
    }
  }
  fillStar(n, 0, 0);

  Print(n);

  return 0;
}