https://www.acmicpc.net/problem/10993
10993번: 별 찍기 - 18
예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.
www.acmicpc.net
재밌어보여서 풀기 시작했다가 복잡해서 당황했다..;;
출력 삼각형을 잘 관찰해보면 가장 큰 삼각형 안에 이전 수준의 삼각형이 있고, 또 그 안에 이전 수준의 삼각형이 있고... 를 반복하는 것을 알 수 있다.
삼각형의 크기는 이전 수준의 삼각형의 대략 2배정도이므로 지수승으로 커진다.
이 점을 이용해서 top-down(재귀) 방식이나 bottom-up(for문) 방식으로 풀면 되는데 나는 for문으로 풀었다.
한줄짜리 string을 저장하는 덱을 선언한 뒤,
가장 작은 삼각형부터 덱에 넣는다.
그리고 그보다 한단계 큰 삼각형을 추가하고 추가하고... 하는 방식으로 풀면 된다.
star랑 space는 그냥 개수를 입력받아서 그 개수만큼 별이나 공백을 반환해주는 함수이다.
시간이 많이 걸린 문젠데 막상 풀고 나니 로직이 그렇게 복잡하진 않은 것 같다.
for문으로 돌 공백 개수만 잘 계산해주면 될 듯!
사실 재귀로 푸는 것이 더 편할거 같다는 생각이 든다.
#include <iostream>
#include <string>
#include <cmath>
#include <deque>
using namespace std;
deque<string> shape;
string star(int a) {
string result;
for (int i = 0; i < a; i++) result += "*";
return result;
}
string space(int a) {
string result;
for (int i = 0; i < a; i++) result += " ";
return result;
}
void draw(int size) {
if (size % 2 == 0) {
// 아랫부분
for (int i = 0; i < shape.size(); i++) {
string result;
result += "*";
result += space(i * 2);
result += shape[i];
result += space(i * 2);
result += "*";
shape[i] = result;
}
shape.push_back(star(pow(2, size + 2) - 3));
//위쪽 삼각형
for (int i = pow(2, size) - 2; i > 0; i--) {
string result;
result += "*";
result += space(i * 2 - 1);
result += "*";
shape.push_front(result);
}
shape.push_front("*");
}
if (size % 2 == 1) {
// 윗부분
for (int i = 0; i < shape.size(); i++) {
string result;
result += "*";
result += space((shape.size() - i - 1) * 2);
result += shape[i];
result += space((shape.size() - i - 1) * 2);
result += "*";
shape[i] = result;
}
shape.push_front(star(pow(2, size + 2) - 3));
//아래쪽 삼각형
for (int i = pow(2, size) - 2; i > 0; i--) {
string result;
result += "*";
result += space(i * 2 - 1);
result += "*";
shape.push_back(result);
}
shape.push_back("*");
}
}
int main() {
int n;
scanf("%d", &n);
shape.push_back("*");
for (int i = 1; i < n; i++) {
draw(i);
}
if (n % 2 == 1) {
for (int i = 0; i < shape.size(); i++) {
cout << space(shape.size() - 1 - i);
cout << shape[i] << "\n";
}
}
if (n % 2 == 0) {
for (int i = 0; i < shape.size(); i++) {
cout << space(i);
cout << shape[i] << "\n";
}
}
}
'Algorithm > 백준' 카테고리의 다른 글
[백준] 5430번: AC (0) | 2020.03.19 |
---|---|
[백준] 3078번: 좋은 친구 (0) | 2020.03.19 |
[백준] 3190번: 뱀 (0) | 2020.03.12 |
[백준] 5397번: 키로거 (0) | 2020.03.12 |
[백준] 1021번: 회전하는 큐 (0) | 2020.03.12 |