https://www.acmicpc.net/problem/2448
예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.
첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수)
첫째 줄부터 N번째 줄까지 별을 출력한다.
별 찍기-10번 문제를 풀었다면 알고리즘을 구상하는데에 큰 어려움은 없을 것이다.
먼저 주의사항이 있는데 삼각형의 왼쪽 오른쪽 공백은 반드시 출력해야한다.
나는 이 공백들을 재귀가 시작되기전, 끝난후에 출력해줌으로써 해결하였다.
규칙을 찾을 때 헷갈리는 공백을 제거한 삼각형의 모양을 보면 다음과 같다.
여기서 규칙을 찾아보면 다음과 같다.
1. 가운데 공백 삼각형과 나머지 삼각형으로 나눌 수 있다.
2. 가운데 삼각형을 제외한 나머지 삼각형들은 서로 모양이 같다.
따라서 재귀를 실행할 때 가운데 삼각형이 아니라면 좌표값을 조정하고 크기를 1/3로 줄인 후
위쪽 삼각형을 기준으로 다시 재귀를 실행한다.
또한 제일 작은 삼각형인 N=3일 때의 최소값 조건문을 넣어준다.
#include <iostream>
using namespace std;
void recurse(int x, int y, int size) {
if (size == 3) {
if (x == 1 && y == 1)
cout << " ";
else
cout << "*";
return;
}
else {
if (x >= size / 2 && y > (x - size / 2) * 2 && y < size) {
cout << " ";
return;
}
else if (x < size / 2) {
recurse(x, y, size / 2);
}
else if (y <= (x - size / 2) * 2) {
recurse(x - size / 2, y, size / 2);
}
else if (y >= size) {
recurse(x - size / 2, y - size, size / 2);
}
}
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
for (int i = 0; i < N; i++) {
for (int k = N - i - 1; k > 0; k--) {
cout << " ";
}
for (int j = 0; j < 2 * i + 1; j++) {
recurse(i, j, N);
}
for (int k = N - i - 1; k > 0; k--) {
cout << " ";
}
cout << "\n";
}
return 0;
}