백준 2448 - 별 찍기 - 11 (C+)

문제 링크입니다. https://www.acmicpc.net/problem/2448

2448번: 별 찍기 - 11

분할 정복으로 푸는 문제였습니다.

예시로 주어진 삼각형을 같은 모양을 기준으로 계속 나눴습니다.

계속 나누다보면 작은 삼각형 모양이 나오는데, 그것이 기준 모양입니다.

해당 모양을 통해 삼각형이 이루어진 것을 확인할 수 있습니다.

해당 삼각형을 좌표로 생각한 뒤, 각 중심의 좌표를 확인해봤습니다. (해당 그림을 통해 확인해볼 수 있습니다.)

해당 좌표를 통해, 삼각형이 3분류로 어떻게 나눠지는지 확인할 수 있습니다. 

이를 공식으로 나타내보자면, 2번 그림과 같이 나타납니다.

 

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#define INF 210000000000

using namespace std;

int N;
char arr[3][6] = {
	{"  *  "},
	{" * * "},
	{"*****"}
};
char map[3501][6501];
int M = 1;


void count_star(int cnt, int y, int x) {
	if (cnt == 1) {
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 5; j++) {
				map[y + i][x + j] = arr[i][j];
			}
		}
		return;
	}
	count_star(cnt / 2, y, x + 3 * cnt / 2);
	count_star(cnt / 2, y + 3 * cnt / 2, x);
	count_star(cnt / 2, y + 3 * cnt / 2 , x + 3 * cnt);
}

void solve() {
	count_star(N/3 ,0, 0);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N * 2 + 1; j++) {
			if (map[i][j] == '*') cout << "*";
			else cout << " ";
		}
		cout << "\n";
	}
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요