[백준/C,C++] 10993번: 별 찍기 - 18

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

10993번: 별 찍기 - 18

풀이

 

위 그림처럼 별을 찍으면 되는 문제입니다.

 

재귀를 이용해 별을 찍는 문제들에서 배열에 값을 저장한 후 찍는 것이 아닌

 

해당 좌표에 '*' 이 출력돼야 하는지 공백이 출력돼야 하는지 바로 판단하여

 

출력하는 식으로 함수를 구현하려고 했고, 이번 문제 또한 배열을 쓰지 않는 방법으로 해결하였습니다.

 

 

가장 큰 삼각형 단계부터 가장 작은 삼각형 단계까지 재귀 호출합니다.

 

해당 좌표가 현재 삼각형 단계에서 '*' 로 출력될 자리인지 판단하고

 

아니라면 다음으로 작은 삼각형 단계로 재귀 호출하는데, 1 크기의 삼각형이 될 때까지

 

'*' 로 출력될 자리가 아니라면 공백을 출력합니다.

 

 

해당 문제를 풀 때 유의해야 할 점이 있는데 가장 큰 삼각형의 넓이까지만 문자를 출력해야 합니다.

 

아래 이미지들은 4가 입력됐을 때 각 4, 3, 2, 1단계까지만 재귀 호출한 출력 결과를 나타냅니다.

 

?은 아직 해당 좌표에 문자가 정해지지 않았음을 의미합니다.

 

 

 

 

 

 

#include<iostream>
#include<cmath>

using namespace std;

int mid;

void star(int y, int x, int num, int top, int bot)
{
    // 좌변과 우변의 위치
    int left = mid - abs(top - y);
    int right = mid + abs(top - y);
    // y좌표가 하단과 같고 x좌표가 좌변과 우변 범위안에 속해있다면 '*' 출력
    if (y == bot && x >= left && x <= right) cout << '*';
    else if (x == left || x == right) {
        // x좌표가 좌변과 우변의 위치와 같고 y좌표가 상단과 하단 범위안에 속해있다면 '*' 출력
        if ((top > bot ? top : bot) >= y && (top < bot ? top : bot) <= y) cout << '*';
        // 아니라면 공백 출력
        else cout << ' ';
    }
    else {
        // 어디에도 속하지 않는 부분은 공백 출력
        if (num == 1) cout << ' ';
        // 상단과 하단 위치를 갱신하여 재귀 호출
        else star(y, x, num - 1, num % 2 == 0 ? bot + 1 : bot - 1, (top + bot) / 2);
    }
}

int main(void)
{
    int n; cin >> n;
    int height = pow(2, n) - 1;
    int width = height * 2 - 1;
    mid = width / 2;

    for (int i = 0; i < height; i++) {
        for (int j = 0; j < (n % 2 == 0 ? width - i : width - (mid - i)); j++) {
            // 제일 큰 삼각형의 형태가 역삼각형이라면
            if (n % 2 == 0) star(i, j, n, height - 1, 0);
            // 아니라면
            else star(i, j, n, 0, height - 1);
        }
        cout << '\n';
    }

    return 0;
}