백준 2448 별 찍기-11

www.acmicpc.net/problem/2448

2448번: 별 찍기 - 11

 

 

 

 

 

 

<접근방법>

분할정복으로 풀었다.

 

다른 사람들의 코드와 비교했을 때, 분할을 위한 매개변수 세팅이 비효율적이었다.

 

줄 수만으로도 별의 가장 꼭대기 좌표를 설정할 수 있었다.

줄 수는 (별 한 개의 높이) * (별의 개수) 이므로

다음 좌표와 현재 좌표 사이에 상하로 몇 개의 별이 들어갔나 세어보면 되기 때문이다.

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int width[12];
int height[12];
char map[3500][6500];

int retK(int k) {
	int t = 0;
	while (k/2 != 0) {
		t++;
		k /= 2;
	}

	return t;
}

void solve(int y, int x, int k) {
	if (k == 0) {
		map[y][x] = '*';
		map[y+1][x-1] = '*'; map[y+1][x+1] = '*';
		map[y+2][x-2] = '*'; map[y + 2][x-1] = '*'; map[y + 2][x] = '*'; map[y + 2][x+1] = '*'; map[y + 2][x+2] = '*';
		return;
	}
	solve(y, x, k - 1);
	solve(y + height[k - 1], x - width[k - 1] / 2 - 1, k - 1);
	solve(y + height[k - 1], x + width[k - 1] / 2 + 1, k - 1);
}

int main() {
	width[0] = 5;
	height[0] = 3;
	for (int i = 1; i <= 10; i++) {
		width[i] = width[i - 1] * 2 + 1;
		height[i] = height[i - 1] * 2;

	}

	cin >> n;

	int k = n/3;
	k = retK(k);

	solve(0, width[k]/2, k);

	for (int i = 0; i < height[k]; i++) {
		for (int j = 0; j < width[k]; j++) {
			if (map[i][j] == '*') {
				cout << map[i][j];
			}
			else {
				cout << ' ';
			}
		}
		cout << '\n';
	}

	return 0;
}