10993번: 별 찍기 - 18
예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.
www.acmicpc.net
1. 풀이방법
- 재귀를 이용한 별찍기 문제입니다.
- 보통의 별 찍기 문제는 반복문 활용 이고
- 조금 난이도가 있는 별찍기 문제는 재귀+반복문 사용 인경우 가 있습니다.
- 가로와 세로의 길이 (n에따른) 를 먼저 구하고 재귀로 구현하면 되는 문제였습니다.
- 가로는 2^(n+1)-1, 세로는 2^n-1 이였습니다.
- 저는 starmap을 문제 조건 n에 따른 최대치 이상을 이차원 배열로 먼저 선언하였습니다.
2. 주의사항
- 처음 제출하고 "출력형식이 잘못되었습니다" 가 나와 스크롤을 해보았습니다.
-
- 위의 캡처와 같이 바깥쪽 공백은 출력을 하면 안됩니다.
- 저는 이미 이차원배열에 ' '까지 모두 들어가도록 짜서 그냥 출력부에서 홀수,짝수 나누어서 조정해주었습니다.
3. 나의코드
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int n;
char starmap[2048][2048];
int gety(int n) {
int fi = 2;
for (int i = 0; i < n; i++) {
fi *= 2;
}
return (fi - 3);
}
int getx(int n) {
int fi = 2;
for (int i = 0; i < n - 1; i++) {
fi *= 2;
}
return (fi - 1);
}
void makestar(int cnt,int startx,int starty) {
if (cnt == 0) {
return;
}
int cx = getx(cnt);
int cy = gety(cnt);
if (cnt % 2 == 0) { //짝수일때 역삼각형
for (int i = startx; i < startx+cx; i++) {
for (int j = starty; j <starty+ cy / 2 + 1; j++) {
if (i == startx) starmap[i][j] = '*';
else if (j == starty+(i-startx)) starmap[i][j] = '*';
else starmap[i][j] = ' ';
}
}
for (int i = startx; i < startx+cx; i++) {
for (int j = starty+cy / 2+1; j < starty+cy; j++) {
if (i == startx) starmap[i][j] = '*';
else if (j == starty+cy - 1 - (i-startx)) starmap[i][j] = '*';
else starmap[i][j] = ' ';
}
}
makestar(cnt - 1, startx +1, starty + cy / 4+1);
}
else { //홀수
for (int i = startx; i <startx+cx; i++) {
for (int j = starty; j <starty+ cy / 2 + 1; j++) {
if (i == startx+cx-1) starmap[i][j] = '*';
else if (j == starty+(cy / 2) - (i-startx)) starmap[i][j] = '*';
else starmap[i][j] = ' ';
}
}
for (int i = startx; i <startx+cx; i++) {
for (int j =starty+ cy / 2+1; j <starty+ cy; j++) {
if (i ==startx+ cx - 1) starmap[i][j] = '*';
else if (j == starty+(cy / 2) + (i-startx)) starmap[i][j] = '*';
else starmap[i][j] = ' ';
}
}
makestar(cnt - 1, startx + cx / 2, starty + cy / 4+1);
}
}
void printstar(int n) {
int x = getx(n);
int y = gety(n);
if (n % 2 == 1) { // 홀수
for (int i = 0; i < x; i++) {
for (int j = 0; j <= y/2+i; j++) {
cout << starmap[i][j];
}
cout << "\n";
}
}
else { //짝수
for (int i = 0; i < x; i++) {
for (int j = 0; j < y - i; j++) {
cout << starmap[i][j];
}
cout << "\n";
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
makestar(n, 0, 0);
printstar(n);
return 0;
}
- 별찍기 문제의 장점 ! (풀고나서 출력하면 뿌듯하다)
'알고리즘 문제풀이 > 구현' 카테고리의 다른 글
| 백준 17140 [C++] (0) | 2021.01.24 |
|---|---|
| 백준 2726 [C++] (0) | 2021.01.16 |
| 백준 20061 [C++] (0) | 2020.12.28 |
| 백준 20056 [C++] (0) | 2020.12.23 |
| 백준 20055 [C++] (0) | 2020.12.23 |
