Divide & Conquer

문제설명

문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, …)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3^k이며, 이때 1 ≤ k < 8이다.

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

접근

Divide & Conquer(분할정복) 를 활용한 별 찍기 문제이다. N = 3 일때, 기본 모양이 존재하고 3의 거듭제곱인 N에 따라서 반복된다. [백준] 1992번 쿼드트리에서 네 부분으로 나눴던 것을 이번에는 아홉 부분으로 나누어서 재귀적으로 수행하면 쉽게 풀린다.

주의할 점은 널문자(ASCII - 0)와 공백문자(ASCII - 32)를 주의해야한다.(출력하면 똑같이 공백으로 보인다.) 초기화를 공백문자로 하거나 출력할 때 공백문자로 출력하지 않으면 틀렸다고 나온다. 이 부분 때문에 계속해서 틀렸었다…

P.S. [백준] 1780번 종이의 개수 문제와 거의 똑같다.

코드

#include <iostream>
#define MAX_NUM 2200
using namespace std;

char stars[MAX_NUM][MAX_NUM];

void star(int x, int y, int term){
	if(term == 1){
		stars[x][y] = '*';
		return;
	}
	
	int new_term = term/3;
	for(int i=0; i<3; i++){
		for(int j=0; j<3; j++){
			if(i!=1 || j != 1){
				star(x + i*new_term,y + j*new_term, new_term);
			}
		}
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	
	int n;
	cin >> n;
	fill(&stars[0][0], &stars[MAX_NUM-1][MAX_NUM], ' ');
	star(0,0,n);
	
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cout << stars[i][j];
		}
		cout << '\n';
	}
	
	return 0;
}

참고

BOJ #2447
BOJ #1992
[백준] 1992번 쿼드트리
[백준] 1780번 종이의 개수

이 글이 도움이 되셨다면 추천 클릭을 부탁드립니다 :)