백준 10993 [C++]

www.acmicpc.net/problem/10993

10993번: 별 찍기 - 18

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;
}

 

 

- 별찍기 문제의 장점 !   (풀고나서 출력하면 뿌듯하다)