백준 2448 별 찍기 11

작성일 | In |

Problem : 별 찍기 11

유형 : 분할정복, 재귀

문제 해석

  • 규칙을 찾아 별을 출력한다.

문제 재해석

  • 패턴을 보고 규칙을 파악한다.

해결 전략

  • 일정한 삼각형이 프랙탈 형태로 반복되어진다.
  • 어느 한 좌표에서 삼각형이 출력 된다고 생각하면 된다.
  • 좌표를 찾는 것은 분할 정복을 통해 찾는다.

설계, 구현

  • 기본 board를 세팅한다.
  • 높이, 좌표 를 가지고 재귀적으로 탐색한다.
  • 높이가 3인 경우, 삼각형을 출력한다.
  • 높이가 3이 아닌 경우, 높이를 1/2로 줄여본다.
  • 기준점에서, y를 좌측, 우측으로 움직인다.

주의할점

  • NULL과 공백은 다르다.

디버깅

  • 매크로 정의 사용을 주의하자.
  • 만약 #define n 2 * 3 + 1 이 있다면 n 은 7이 아니라 2 * 3 + 1로 대체 될 뿐이다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define MAX (1024 * 3 + 2)
using namespace std;

int n;
char board[MAX][MAX * 2 - 1];

void Print_ans() {
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n * 2 - 1; ++ii) {
            if (board[i][ii] == '*') cout << '*';
            else cout << ' ';
        }
        cout << "\n";
    }
}

void Fill_Star(const int& x, const int& y) {
    board[x][y] = '*';
    board[x + 1][y - 1] = '*', board[x + 1][y + 1] = '*';

    for (int i = y - 2; i <= y + 2; ++i) {
        board[x + 2][i] = '*';
    }
}
void Func(const int& s, const int& x, const int& y) {
    if (s == 3) {
        Fill_Star(x, y);
        return;
    }

    int ns = s / 2;
    Func(ns, x, y);
    Func(ns, x + ns, y - ns);
    Func(ns, x + ns, y + ns);
}

void Solve() {
    Func(n, 0, n - 1);
    Print_ans();
}

void Input() {
    cin >> n;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);
    Input();
    Solve();

    return 0;
}

피드백

  • 배경을 미리 만들어두고, 칠하는 방법을 사용할 수 있다는 것을 배웠다.
  • NULL 을 항상 주의하자
  • 매크로 정의 사용시 주의하자. 다시는 이런 실수를 반복 하지 않도록…
  • 분할 정복은 여전히 굉장히 어렵다.. 연습이 더 필요해 보인다.