2447번 : 별 찍기 - 10 [C++]

문제 링크

성공 여부(걸린 시간): 성공 (12분)

아이디어

나는 재귀를 통해 분할정복을 해주었다. 재귀의 끝에 도달했을때는 1칸에 대한 크기이고
계속해서 중간만 비우도록 중간을 제외한 모든 부분들에 대해서 재귀를 호출하게 된다.

그림으로 보면

만약 N이 9라고 했을때

 

행과 열을 3등분씩해서 이런식으로 9등분을 하게 된다. 

왜 3등분을 하는가? 

최소단위로 나누었을때도 그렇고 아닐때도 그렇고 패턴은 항상 빨간 색으로 표시해둔 부분이 중간을 제외하고

모두 존재하는 것을 확인할 수 있다.

그래서 내가 생각한 것은 

void print_star(int len, int x, int y) {
	if (len==1) {
		arr[x][y] = 1;
		return;
	}
	int new_len = len / 3;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j <  3; j++) {
			if (i==1 && j==1) {
				continue;
			}
			print_star(new_len, x + i * new_len, y + j * new_len);
		}
	}

}

중간인 경우는 continue해주고 나머지 부분들에 대해서는 시작점을 주고 현재 len의 3등분한 값에 맞게 재귀를 호출하게 된다.

 

풀이 코드

#include<iostream>
using namespace std;

int arr[3000][3000] = { {0,},};

void print_star(int len, int x, int y) {
    if (len==1) {
        arr[x][y] = 1;
        return;
    }
    int new_len = len / 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j <  3; j++) {
            if (i==1 && j==1) {
                continue;
            }
            print_star(new_len, x + i * new_len, y + j * new_len);
        }
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;

    print_star(N, 0, 0);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            char x = arr[i][j] == 1 ? '*' : ' ';
            cout << x;
        }
        cout << "\n";
    }

    return 0;
}