별찍기-10
문제
재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.
크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.
***
* *
***
N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력과 같다.
입력
첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.
예제 입력 및 출력
입력
27
출력
소스 코드
#include <iostream>
using namespace std;
int N;
void Star(int size, int line) {
// 1사이즈는 점만 찍고 탈출
if (size == 1) {
cout << '*';
return;
}
//1번~size번 줄 순회
for (int i = line; i < size; i++) {
//최초 함수가 아니면 해당 라인 한줄만 출력
if (size != N && i > line)
return;
//한줄에 3번 재귀함수 호출
for (int j = 0; j < 3; j++) {
//가운데 비는 부분은 재귀 호출 안함
if (i >= size / 3 && i < size / 3 * 2 && j == 1) {
//size별로 공백의 크기가 달라짐
for (int k = 0; k < size / 3; k++)
cout << ' ';
continue;
}
//재귀 호출
Star(size / 3, i % (size/3));
}
//최초 함수 한줄 끝나면 개행
if (size == N) {
cout << endl;
}
}
}
int main(void) {
cin >> N;
Star(N, 0);
}문제 풀이
1. 초기 아이디어
-
처음에는 size=27 의 사각형을 그리려면 size = 9인 사각형을 9개 호출하고 또 재귀 함수를 통해 size=3인 사각형을 만드는 함수를 각각 9개씩 호출하면 쉽게 풀릴 거라 생각했지만, 이 방식으로 하면 서로 다른 함수를 같은 줄에 연속해서 출력할 수 없기 때문에 다른 방식으로 재귀 함수를 구상하였다.
2. 함수 탈출 조건
-
size = 1 이면 가장 작은 크기로 분해되었으므로 '*'만 찍고 함수를 탈출한다.
3. 문제 해결 방법
-
초기 함수에서 size가 주어지면 0번째 줄부터 size-1번째 줄까지 순회하여 한줄씩 재귀 함수를 호출하여 사각형을 만든다.
-
초기 호출한 함수가 아닌데 0번째 줄부터 size-1번째 줄까지 순회하여 호출하게 되면 다음줄로 넘어가게 되어 1줄씩 채우는 형태로 재귀 함수를 구상할 수 없다.
-
초기 호출한 함수가 아니면 인자로 받은 line 한줄만 출력하고 탈출한다. ex) size = 9의 두 번째 줄을 채우고 있는 경우(예시 4번 순서) Star(size=3, line=2)의 함수를 호출하여 size가 3인 사각형의 두 번째 라인만 한 줄 호출하여 별을 찍고 함수를 탈출하게 된다.
-
-
한 줄을 채울 때 총 3번의 동일한 재귀 함수를 호출해야 한다.
-
ex) 예시에서 첫번째 줄을 호출하기 위해서는 Star(size=3, line 1)의 함수를 3번 호출함 -> 3번 호출하여 1, 2, 3 순서를 채움
-
-
재귀호출문 2번째 인자에서 i % (size/3)인 이유 -> line값(i)이 계속 증가하지만 재귀 호출하게 되면 결국 같은 line이 반복됨
-
ex) size = 27인 사각형에서 0번째 줄과 9번줄은 size = 9인 사각형의 0번 줄을 3개 이어 붙여 구성하기 때문에 결국 같은 Star(size=9, line=0) 함수를 호출하여 채우게 됨
-
문제 출처 : https://www.acmicpc.net/status?from_problem=1&problem_id=2447