(C/C++) 백준 2447번 - 별 찍기 -10

문제출처: https://www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

1. 코드

#include <iostream>
#include <algorithm>
#include <string>
 
using namespace std;
 
void star(int i, int j, int n) {
    if (i % 3 == 1 && j % 3 == 1) {
        printf(" ");
        return;
    }
    else if (n == 1) {
        printf("*");
        return;
    }
    else star(i / 3, j / 3, n / 3);
    
 
    //N*N 의 배열 만들어주고 배열에 공백으로 채움
    // 3의 제곱값을 입력 받고 3으로 나눠서 1이 될때까지 나눠준다.
    // 1이 될때까지 나눈 값들은 *을 입력
 
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            star(i, j, n);
        }
        printf("\n");
    }
    return 0;
}

 

2. 해결방법

그림을 그려서 직접 규칙을 찾아서 풀었다.

3*3 배열의 경우 가운데를 비워줘야한다. 9*9 배열의 경우에 공백을 출력해야하는 좌표를 찾아보면, 3*3과 마찬가지로 가운데가 빈칸이며, 중앙에 3*3으로 크게 빈 부분이 나타나는 규칙을 가진다. 좌표로 나타내면

(1,1),(1,4),(1,7)

(3,3), (3,4), (3,5), (4,3), (4,4), (4,5), (5,3), (5,4), (5,5)

(7,1),(7,4),(7,7)

이다. 즉, 빈칸으로 출력해야하는 조건은 (i%3)==1&&(j%3)==1 이다.

 

3. 느낀점

재귀는 어렵다.. 규칙을 찾는 것이 생각보다 까다로웠고, 분할정복 알고리즘을 사용해야한다는 것을 검색을 통해서 알게되었던 문제였다. 공부를 더 많이 해야한다...