백준 2447(별 찍기-10)

jh Seo·2022년 7월 19일

백준 분할 정복 한번에 못 푼 문제

백준

목록 보기

25/180

개요

[링크]백준 2447번: 별 찍기 -10

입력
첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.
출력
첫째 줄부터 N번째 줄까지 별을 출력한다.

접근 방식

첫 번째 방식은
재귀를 이용한 방식으로 x좌표, y좌표, 각 변의 길이를 매개변수로 받는 재귀 함수를 이용했다.

매 재귀마다 사각형을 9부분으로 나눠서 가운데 빈 부분만
제외하고 나머지 8부분만 재귀로 구현한 후,

각 변의 길이가 1일때 * 을 출력하게 구현했더니
세번째마다 줄바꿈을하고 다시 예전 좌표로 돌아가게 구현을
해야해서 너무 까다로웠다.
두 번째 방식은
중앙에 빈 칸인 나오는 규칙을 찾아서 구현하는 방식이다.
각 재귀에서 사각형 변의 길이가 L이라 하고,
각 재귀에서 빈 칸에 해당하는 좌표를 편의상 (x,y)라 하면
x/L과 y/L을 3으로 나눴을 때 나머지가 1이라는 규칙이 나온다.
세 번째 방식은
최대 범위가 3^8승인 점을 생각해
2187 * 2187 크기의 배열을 생성해서 푸는 방식이다.
각 재귀에서 사각형 변의 길이가 3일 때
가운데가 빈 사각형을 출력하는 방식이다.

배열을 통해 좌표를 직접 설정해서 할 수 있으므로
제일 직관적이다.

두 번째 방식 코드

#include<iostream>												
																
																
using namespace std;

void input(int& amount) {
	cin >> amount;
}

void solution(int x, int y, int length) {	//비어있는 좌표를 다적어보면 빈 좌표 / 해당 사각형 길이를 3으로 나눴을때
											// 1이나온다는 공통점이있다는걸 활용한풀이
	if ((x / length) % 3 == 1 && (y / length) % 3 == 1) {
		cout << " ";
	}
	else
	{
		if (length / 3 == 0)
			cout << "*";
		else
			solution(x, y, length / 3);
	}
		

}
	

int main() {
	int amount = 0;
	input(amount);
	for (int i = 0; i < amount; i++) {
		for (int j = 0; j < amount; j++) {
			solution(i, j, amount);
		}
		cout << '\n';
	}
}

세 번째 방식 코드

#include<iostream>

using namespace std;

char arr[2188][2188];

void input(int& inputN) {
	cin >> inputN;
}
void init(const int& inputN) {
	for (int i = 0; i < inputN; i++) {
		for (size_t j = 0; j < inputN; j++)
		{
			arr[i][j] = ' ';
		}
	}
}
void solution(int x, int y, int length) {
	if (length == 3) {
		arr[x][y] = '*';
		arr[x][y + 1] = '*';
		arr[x][y + 2] = '*';
		arr[x + 1][y] = '*';
		arr[x + 2][y] = '*';
		arr[x + 1][y + 2] = '*';
		arr[x + 2][y + 2] = '*';
		arr[x + 2][y + 1] = '*';
	}
	else {
		solution(x, y, length / 3);
		solution(x, y+ length / 3, length / 3);
		solution(x, y+2* length / 3, length / 3);
		solution(x+ length / 3, y, length / 3);
		solution(x+ length / 3, y+2* length / 3, length / 3);
		solution(x+ 2*length / 3, y, length / 3);
		solution(x+ 2*length / 3, y+ length / 3, length / 3);
		solution(x+ 2*length / 3, y+2* length / 3, length / 3);
	}

}
void print(const int& amount) {
	for (int i = 0; i < amount;i++) {
		for (int j = 0; j < amount; j++) {
			cout<<arr[i][j];
		}
		cout << '\n';
	}
}

int main() {
	int amount;
	input(amount);
	init(amount);
	solution(0, 0, amount);
	print(amount);

}