728x90
별을 찍는 문제입니다.
3의 n제곱으로 입력을 받습니다.
3의 입력값은 다음 모양을 가집니다.
★ | ★ | ★ |
★ | ★ | |
★ | ★ | ★ |
9의 입력값은 다음 모양을 가집니다.
★ | ★ | ★ | ★ | ★ | ★ | ★ | ★ | ★ |
★ | ★ | ★ | ★ | ★ | ★ | |||
★ | ★ | ★ | ★ | ★ | ★ | ★ | ★ | ★ |
★ | ★ | ★ | ★ | ★ | ★ | |||
★ | ★ | ★ | ★ | |||||
★ | ★ | ★ | ★ | ★ | ★ | |||
★ | ★ | ★ | ★ | ★ | ★ | ★ | ★ | ★ |
★ | ★ | ★ | ★ | ★ | ★ | |||
★ | ★ | ★ | ★ | ★ | ★ | ★ | ★ | ★ |
여기서 알 수 있는점은
3은 가운데가 비어있고 나머지를 별로 채운 모양입니다.
9는 3*3모양씩 잘라서 생각했을때 가운데가 비어있고
나머지는 3을 입력했을때의 모양으로 채워져있습니다.
27을 입력한다면 9*9의 모양으로 잘라서 보았을때 가운데가 비어있고
나머지는 9를 입력했을때의 모양으로 채워져 있을것입니다.
이 문제는 분할 정복 알고리즘으로 문제를 해결합니다.
n*n배열을 만들어주어서 그 배열에 공백으로 가득채웁니다.
3의 제곱값을 입력받고 그 값을 3으로 나누어서 1이 될때까지 나눕니다.
1이 될때까지 나누어진 값들은 배열에 *을 채워줍니다.
1이 되지 못하는 경우는 i와 j가 1일때인데 이는 현재 n*n배열에서 중앙을 의미합니다.
모든값들이 배열에 입력되었으면 출력해주면서 별 찍기를 완성합니다.
#include <iostream>
using namespace std;
char map[3000][3000];
void init() {
for (int i = 0; i < 3000; ++i) {
for (int j = 0; j < 3000; ++j) {
map[i][j] = ' ';
}
}
}
void solve(int n, int x, int y) {
if (n == 1) {
map[x][y] = '*';
return;
}
int div = n / 3;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (i == 1 && j == 1) {
continue;
}
solve(div, x + (div * i), y + (div * j));
}
}
return;
}
int main(int argc, char *argv[])
{
int n;
cin >> n;
init();
solve(n, 0, 0);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << map[i][j];
}
cout << endl;
}
return 0;
}
'알고리즘' 카테고리의 다른 글
[C++] 백준 2193번 이친수 (0) | 2019.05.17 |
---|---|
[C++] 백준 1149번 RGB거리 (0) | 2019.05.09 |
[C++] 백준 1669번 멍멍이 쓰다듬기 (0) | 2019.05.05 |
[C++] 백준 1947번 선물 전달 (0) | 2019.05.05 |
[C++] 백준 2579번 계단 오르기 (0) | 2019.05.03 |