[baekjoon 2447] 별 찍기 - 10 (재귀 호출) (C++)

www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

재귀를 이용해서 별 찍기 문제이다.

그림처럼 사이즈가 3일 때는 가운데만 뚫려있고, 나머지 case는 재귀적으로 주위에 이전 단계 도형이 그려지고 가운데가 뚫려있게끔 출력하면 된다.

사이즈가 27이면 주변이 위에 있는 사이즈 9의 도형이 둘러싼다.

 

 

처음엔 재귀를 이용하되, 함수 자체에서 cout을 하면 되겠다고 생각했지만, 개행을 해주면 재귀적으로 출력을 하기 힘들다고 판단했고, 2차원 배열에 저장한 뒤 나중에 한꺼번에 출력하게끔 풀었다.

 

가운데에 공백을 넣는 조건을 생각했는데, 재귀 호출을 할 때 row와 col을 사용하다 보니 공백을 유연하게 출력하지 못하겠다고 생각해서 아예 2차원 배열을 공백으로 초기화해주었다.

 

그 이후에는 사이즈가 3의 제곱수이기 때문에 3씩 나눠주면서 호출해주었다.

 

1. 사이즈가 3일 때(base case)

 - 그림과 같이 주변은 *을 저장하고 가운데가 뚫려있는 3X3 도형을 출력한다.

2. 사이즈가 3보다 클 때

 - 주변에 *을 저장하는 것이 아닌 base case 도형이 출력이 돼야 하므로 이 경우에 재귀 호출을 진행해준다.

 

설계만 잘하면 복잡하게 생각 안 해도 출력이 잘 되는 것을 볼 수 있다.

 

#include <iostream>

using namespace std;
int n;
char star[6562][6562];

void printStar(int col, int row, int size) {
	int tempsize = size / 3;
	if (size == 3) {
		for (int i = col; i < col+size; i++) {
			for (int j = row; j < row+size; j++) {
				if (i >= col+tempsize && i < col+tempsize * 2 && j >= row+tempsize && j < row+tempsize * 2) {
					star[i][j] = ' ';
				}
				else {
					star[i][j] = '*';
				}
			}
		}
	}

	else {
		for (int i = col; i < col + size; i += tempsize) {
			for (int j = row; j < row + size; j+= tempsize) {
				if (i >= col + tempsize && i < col + tempsize * 2 && j >= row + tempsize && j < row + tempsize * 2) {
					star[i][j] = ' ';
				}
				else {
					printStar(i, j, tempsize);
				}
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			star[i][j] = ' ';
		}
	}

	printStar(0,0,n);

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

}

재귀 호출의 시작은 0,0부터 해준다.

이후 2차원 배열에 저장하고, 출력해준다.