백준 16505 별

작성일 | In |

Problem : 별

유형 : 분할정복, 재귀

문제 해석

  • 별을 찍는 규칙을 찾아라.

문제 재해석

  • 예제를 보고 규칙을 찾는다.
  • 줄 끝에는 필요없는 공백을 출력하지 않는다.

해결 전략

  • 자기의 모습을 copy 하여, 오른족 , 아래쪽 좌표에 이어 붙이는 프랙탈 형태이다.
  • 즉 분할 정복 으로 해결이 가능하다.
  • 커지는 단위는 2^n인것을 규칙을 통해 유추해 낼 수 있다.

설계, 구현

  • 처음에 전부 공백으로 칠해놓는다.
  • { 0 , 0 } 을 기준으로, 본인 크기가 1 이 된경우에만 해당 좌표에 별을 찍는다.
  • 1 보다 큰 경우에는, 본인 크기를 절반으로 자른 뒤, 잘라진 크기만큼 x 혹은 y 좌표를 이동 한뒤, 해당 지점을 시작점으로 잡고 별찍기를 시도한다.
  • 또한 { 0 , 0 } 기준으로, 잘라진 크기만큼 또 별찍기를 시도한다.

주의할점

  • 각 줄 끝에는 필요없는 공백을 출력하지 않는다. 조건을 놓치면 안된다.
  • 즉, 입력이 1인경우 {1,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
57
#include <bits/stdc++.h>
using namespace std;

char board[1300][1300];
int n;

void PrintAnswer() {
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n - i; ++ii) {
            cout << board[i][ii];
        }
        cout << "\n";
    }
}

void Func(int s, int x, int y) {
    if (s == 1) {
        board[x][y] = '*';
        return;
    }
    
    int ns = s / 2;
    Func(ns, x, y);
    Func(ns, x + ns, y);
    Func(ns, x, y + ns);
}

void Solve() {
    Func(n, 0, 0);
    PrintAnswer();
}

void Init() {
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii) {
            board[i][ii] = ' ';
        }
    }
}

void Input() {
    cin >> n;
    n = 1 << n;
    Init();
}

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

    Input();
    Solve();

    return 0;
}

피드백

  • 실버5 문제임에도 굉장히 애를 먹었다.
  • 재귀 트레이닝이 더 필요해 보인다.