백준 2447번 별 찍기 - 10

문제 링크 : https://www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

 

문제

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

 

입력

첫째 줄에 N이 주어진다. N은 항상 3의 제곱꼴인 수이다. (3, 9, 27, ...) (N=3^k, 1 ≤ k < 8)

 

출력

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

 

예제 입력

27

 

예제 출력

풀이

분할 정복 문제이다.

예제 출력을 자세히 보면 가운데가 뻥 뚫린 모양의 직사각형인데

입력으로 주어진 N = 3^k에서 k의 크기가 클수록 직사각형의 규모가 커지고,

그 안에 3^(k-1) 가 9개 존재하는 것을 볼 수 있다. k가 1 증가할 수록 규모가 가로 3 세로 3씩 곱해져서 커지기 때문이다. 따라서 이 문제는 k값을 구하고, k를 인자로 재귀호출할 때마다 사각형을 9등분해 k를 1씩 줄여나가면서 그려주면 된다. 단, 가운데 사각형은 공백 처리를 해줘야한다.

공백 처리부분은 코드를 보며 설명하겠다.

 

소스 코드

#include <iostream>
using namespace std;
 
char star[2500][2500];
int n;
void put_star(int y, int x, int squard, int check) {
    if (squard == 0) {
        if (check == 1) star[y][x] = ' ';
        else star[y][x] = '*';
        return;
    }
    else {
        int t = 1;
        for (int i = 0; i < squard - 1; i++) {
            t *= 3;
        }
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i == 1 && j == 1) put_star(y + (i * t), x + (j * t), squard - 1, 1);
                else {
                    if (check == 1) put_star(y + (i * t), x + (j * t), squard - 1, 1);
                    else put_star(y + (i * t), x + (j * t), squard - 1, 0);
                }
            }
        }
    }
}
 
void print_star() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%c", star[i][j]);
        }
        printf("\n");
    }
}
int main()
{
    scanf("%d", &n);
    int squard = 0;
    int temp_n = n;
    while (temp_n != 1) { //3의 제곱 수 구하기
        temp_n /= 3;
        squard++;
    }
    put_star(0, 0, squard, 0);
    print_star();
    return 0;
}

put_star 함수가 재귀함수 부분이다.

기저사례로 만약 제곱 수가 0이라면 크기가 1x1이므로 출력한다.

공백 부분을 처리하기 위해서 이중 for문으로 재귀호출 시 i = 1, j = 1일 때는 따로 만든 int check를 1로 두고 넘기게 하였고, 기저사례에 도착했을 때 check가 1이면 공백을 넣기로 하였다.

이후에 함수를 계속 재귀하여도 한 번 check가 1이 된건 변하지 않게 하기 위해서 check == 1인건 따로 나누어 처리하도록 하였다.

 개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~