백준 2448 별찍기-11 c++ // 재귀함수, 분할정복법

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

2448번: 별 찍기 - 11

0. 함수정의

크기, 시작좌표에 별을 그리는 함수

//좌표기준 : 좌측위 기준
void go(int n, int y, int x) {

 

 

1. 세로 : n / 가로 : 2n-1 이다.

ex) n==3일때 생각

 

2. 기저사례

n==3일때, 더이상 쪼갤수 없다.

좌표로 별을 그리면 된다.

 

3. 재귀식

go(12) == go(6) go(6) go(6)  3개로 분할 가능하다.

검은사각형 == 파란사각형3개로 분할한다.

검은사각형의 시작 좌표를 x,y라고 할때,

시작좌표1 : x,y+half

시작좌표2 : x +half ,y

시작좌표3 : x +half ,y+half *2

 

int half = n / 2;

//재귀식
//위삼각형의 첫좌표
go(half, y, x+half);
//좌측아래삼각형의 첫좌표
go(half, y + half, x );
//우측아래삼각형의 첫좌표
go(half, y + half, x + n);

 

4. 주의사항

전역변수는 null로 초기화 - > map을 빈칸으로 초기화 해줘야 제대로 출력된다.

//빈칸으로 초기화해야 제대로 출력됨!
for (int i = 0; i < n; ++i) fill(a[i], a[i] + n*2, ' ');

 

 

5. 전체코드

#include <bits/stdc++.h>
using namespace std;

char a[3100][6200];
int n;

//좌표기준 : 좌측위 기준
void go(int n, int y, int x) {

	if (n == 3) {

		a[y][x+2] = '*';

		a[y + 1][x + 1] = '*';
		a[y + 1][x + 3] = '*';

		a[y + 2][x] = '*';
		a[y + 2][x + 1] = '*';
		a[y + 2][x+2] = '*';
		a[y + 2][x +3] = '*';
		a[y + 2][x +4] = '*';


		return;
	}

	int half = n / 2;

	//재귀식
	//위삼각형의 첫좌표
	go(half, y, x+half);
	//좌측아래삼각형의 첫좌표
	go(half, y + half, x );
	//우측아래삼각형의 첫좌표
	go(half, y + half, x + n);



}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	//빈칸으로 초기화해야 제대로 출력됨!
	for (int i = 0; i < n; ++i) fill(a[i], a[i] + n*2, ' ');

	go(n, 0,0);

	//가로길이 : 2n-1 
	//n==3 일때를  생각하면 쉽다
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n*2; ++j) {
			cout << a[i][j];
		}
		cout << "\n";
	}
	
}