[BOJ] 2448 - 별 찍기 - 11

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

BOJ - 별 찍기 - 11

문제 유형: 재귀, 구현

문제 난이도: Gold IV

시간 제한: 1초

메모리 제한: 256MB

 

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

 

입력

첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수)

 

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

 

풀이

 

재귀적인 방법, 반복적인 방법 모두 가능하다.

 

반복적인 풀이:

shape = {

"  *  "

" * * "

"*****"

}

를 처음에 저장해놓고, shape의 크기가 n이될때까지 계속해서 크기를 증식시킨다.

매번 길이가 두 배가 되는데,

shape[i + 기존높이] = shape[i] + " " + shape[i]의 꼴로 다음 새로운 파트를 만들 수 있다.

그리고, 양쪽 공백을 채우기 위해, shape[i] = (" "를 기존높이번) + shape[i] + (" "를 기존높이번) 한 것을 저장해놓으면 된다.

 

최종적인로 완성된 shape를 출력한다.

 

재귀적인 풀이:

n * 2n-1짜리 배열을 미리 만들어놓는다.

draw_triangle(n, x, y, shape)를 호출한다. 처음에는 전체 높이의 첫 줄의 가운데이므로, draw_triangle(n, 0, n-1, shape)를 호출한다.

base case:: n이 3이면, 현재 좌표를 기준으로 기본 삼각형을 만든다. 현재 좌표, 그 다음 행의 +-1열, 그 다음행의 -2부터+2열까지 전부 '*'으로 채운다.

그게 아니라면, 분할해서 재귀 호출한다.

절반 값인 half = n/2를 구해서,

draw_triangle(half, x, y, shape), 

draw_triangle(half, x + half, y - half, shape), 

draw_triangle(half, x + half, y + half, shape)를 호출한다.

각각 위쪽, 왼쪽, 오른쪽 부분삼각형을 구성하라는 의미이다.

 

최종적으로 완성된 shape를 출력한다.

 

코드

C++

 

반복 풀이

#include <bits/stdc++.h>

using namespace std;

int len;
void scaleup(int height, vector<string> &shape) {
  for (int i = 0; i < height / 2; ++i) {
    string temp = "";
    temp += shape[i] + " " + shape[i];
    shape.emplace_back(temp);
    shape[i] = string(height / 2, ' ') + shape[i] + string(height / 2, ' ');
  }
}

void solve(int n) {

  vector<string> shape = {"  *  ", " * * ", "*****"};

  int height = 6;
  while (height <= n) {
    scaleup(height, shape);
    height *= 2;
  }
  for (int i = 0; i < n; ++i) {
    cout << shape[i] << "\n";
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int n;
  cin >> n;
  len = n * 2 - 1;
  solve(n);
  return 0;
}

 

재귀 풀이

#include <bits/stdc++.h>

using namespace std;

void draw_triangle(int n, int x, int y, vector<string> &shape) {
  if (n == 3) {
    shape[x][y] = '*';
    shape[x + 1][y - 1] = '*';
    shape[x + 1][y + 1] = '*';
    for (int i = -2; i <= 2; i++)
      shape[x + 2][y + i] = '*';
    return;
  }

  int half = n / 2;
  draw_triangle(half, x, y, shape);
  draw_triangle(half, x + half, y - half, shape);
  draw_triangle(half, x + half, y + half, shape);
}

void solve(int n) {
  vector<string> shape(n, string(2 * n - 1, ' '));

  draw_triangle(n, 0, n - 1, shape);

  for (int i = 0; i < n; ++i) {
    cout << shape[i] << "\n";
  }
}

int main() {
  int n;
  cin >> n;
  solve(n);
  return 0;
}