백준 2447 : 별 찍기 - 10

혀니앤·2021년 10월 2일
0

C++ 알고리즘

목록 보기
76/118

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

1. 접근

  • 재귀를 사용하여 구하라고 했으므로, 분할정복으로 접근한다.
  • N 전체를 표현하기 위해서는 결국 3의 제곱수일때의 패턴들이 반복된다.
  • N을 계속 3으로 나누고 N*N 에서 가운데를 비우는 과정들을 반복해야 한다.
  • 앞선 문제들과는 다르게, 가장 작은 크기는 3*3 모양이므로 크기가 3보다 작아질때까지 반복한다.
    (앞선 문제에서는 모두 일치하지 않는 등의 조건에 따라 반복하고, 모두 확인하면 끝낼 수 있었다.)

2. 나의 풀이

#include <iostream>
#include <cstring>
#define MAX 2200
using namespace std;

int n;
bool star[MAX][MAX];

void divide(int x, int y, int size) {
	int blanksize = size / 3;
	for (int i = x+ blanksize; i < x+ blanksize *2; i++) {
		for (int j = y+ blanksize; j < y + blanksize *2; j++) {
			star[i][j] = false;
		}
	}
}

void check(int x, int y, int size) {
	if (star[x][y]) {
		divide(x, y, size);

		int newsize = size / 3;
		if (newsize == 1) return;
		for (int i = x; i <= x + newsize*2; i+=newsize) {
			for (int j = y; j <= y + newsize*2; j+=newsize) {
				check(i, j, newsize);
			}
		}
	}
}

void printStar() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (star[i][j]) cout << "*";
			else cout << " ";
		}
		cout << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		memset(star[i], true, n);
	}
	

	check(0, 0, n);
	printStar();
	return 0;
}
profile
일단 시작하기

0개의 댓글