[백준(BOJ)] 2447번 C++ 풀이

오늘도 이어서 간단한 알고리즘 문제를 풀어보려고 한다. 

이전 내용과 동일하게 재귀함수 관련 문제이다.

 

 

[문제 풀이]

일단 규칙성을 확인해봐야 할 것 같다. 가장 작은 도형부터 시작하자.

 

가운데 부분만 비어있고 나머지는 채워져 있음을 알 수 있다. 이를 한줄로 이어보자.

 

비어 있는 칸은 차례대로 (1, 1), (1, 4), (1, 7), (1, 10), (1, 13), (1, 16) ... 이다.

이는 j % 3 == 1 일 떄 빈칸이라는 말과 동일하다.

같은 방식이 아래쪽, i에도 적용되므로

i % 3 == 1 && j % 3 == 1 을 만족할 때 좌표는 비어있게 된다. 

이제 이를 확장해 n=9일 때를 살펴보자.

 

 

비어 있는 공간은 기본 빈 공간에 더해

(3, 3), (3, 4), (3, 5)

(3, 3), (3, 4), (3, 5)

(3, 3), (3, 4), (3, 5)

인데 이는

 

 

위와 같은 3 x 3 구조의 표에서 가운데를 빈 공간으로 하는 이전 방식과 동일하다.

따라서 이를 일반화 시키려면 i와 j를 n으로 나눈 몫이 3으로 나누었을 때 나머지가 1인지를 살펴보면 된다.

(i /n) % 3 ==1 && (j / n) % 3 == 1 을 몬작할 때 좌표는 비어 있다.

 

#include <iostream>
using namespace std;


int star(int i, int j, int n);

int main( ){
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++)
			star(i, j, n);
		cout << '\n';
	}
    return 0;
}

int star(int i, int j, int n){
	if((i / n) % 3 == 1 && (j / n) % 3 == 1)
		cout << " ";
	else if(n / 3 == 0)
		cout << "*";
	else
		star(i, j, n / 3);
	return 0;
}

 

n으로 빈칸을 검사했을 때 n / 3으로 검사해도 마찬가지로 빈칸이므로 빈칸은 바로 출력하고, 빈칸이 아닌 경우 재귀적으로 star(i, j, n / 3)으로 반복해 빈칸을 검사한다.

※ 이때 n / 3 == 0 이라는 뜻은 3 x 3 구조에서 위의 빈칸 조건이 만족하지 않을 때 나머지를 * 표시 하라는 의미이다. (가운데만 뚫려있고 나머지는 * 로 둘러싸여 있다는 점을 생각하자)