백준 2447 : 별 찍기 - 10
https://www.acmicpc.net/problem/2447
1. 접근
- 재귀를 사용하여 구하라고 했으므로, 분할정복으로 접근한다.
- N 전체를 표현하기 위해서는 결국 3의 제곱수일때의 패턴들이 반복된다.
- N을 계속 3으로 나누고 N*N 에서 가운데를 비우는 과정들을 반복해야 한다.
- 앞선 문제들과는 다르게, 가장 작은 크기는 3*3 모양이므로 크기가 3보다 작아질때까지 반복한다.
(앞선 문제에서는 모두 일치하지 않는 등의 조건에 따라 반복하고, 모두 확인하면 끝낼 수 있었다.)
2. 나의 풀이
#include <iostream>
#include <cstring>
#define MAX 2200
using namespace std;
int n;
bool star[MAX][MAX];
void divide(int x, int y, int size) {
int blanksize = size / 3;
for (int i = x+ blanksize; i < x+ blanksize *2; i++) {
for (int j = y+ blanksize; j < y + blanksize *2; j++) {
star[i][j] = false;
}
}
}
void check(int x, int y, int size) {
if (star[x][y]) {
divide(x, y, size);
int newsize = size / 3;
if (newsize == 1) return;
for (int i = x; i <= x + newsize*2; i+=newsize) {
for (int j = y; j <= y + newsize*2; j+=newsize) {
check(i, j, newsize);
}
}
}
}
void printStar() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (star[i][j]) cout << "*";
else cout << " ";
}
cout << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
memset(star[i], true, n);
}
check(0, 0, n);
printStar();
return 0;
}
Author And Source
이 문제에 관하여(백준 2447 : 별 찍기 - 10), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jeongopo/백준-2447-별-찍기-10저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)