[2447] 백준 : 별 찍기 - 10(C++)

개인적으로 여태 푼 문제중 가장 이해가 안 되고 가장 오래고민했으나 결국 못 풀고 구글링해서 푼 문제다..ㅠㅠ

 

* 접근 방법
- 분할정복 알고리즘을 이용하자!

▶ 분할 정복 알고리즘?
- 주어진 문제를 작은 문제로 나누고(Divide) 각각의 작은 문제를 해결(Conquer)하는 것
  1. 문제를 하나 이상의 작은 문제로 분할
  2. 작은 문제들의 해답을 각각 구함(재귀함수 이용)
  3. 작은 문제의 답을 통합하여 원래의 문제의 답을 구함

 

* 문제 분석

1) n=3인 경우
   └ 별이 ㅁ 모양으로 반복

2) n=9인 경우
   └ n=3인 경우가 ㅁ모양으로 반복

3) n=27인 경우
   └ n=9인 경우가 ㅁ모양으로 반복

즉, 
   1. 입력한 숫자n(가로, 세로)을 3으로 나누어 9개로 분할
   2. 정중앙의 큰 빈칸을 제외하고 나머지 칸은 재귀함수로 처리 

 

* 풀이

   - 공백의 좌표 : (1, 1), (1, 4), (1, 7), (1, 10), (1, 13), (1, 16), (1, 19), · · ·  
                  -  : (4, 1), (4, 4), (4, 7), (4, 10), (4, 13), (4, 16), (4, 19), · · ·
                       ☞ ( x % 3 ==1 ) && ( y % 3 ==1 )

   
   - 공백의 좌표 : (3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5)
                        = ( (x / 3) % 3 ==1 ) && ( (y / 3) % 3 ==1 )
 -  ㄴㄴㄴㄴ      : (9, 9), (9, 10), · · ·, (9, 17), (10, 9), · · ·, (10, 17), · · ·, (17, 17)
                        = ( (x / 9) % 3 ==1 ) && ( (y / 9) % 3 ==1 )
                      ☞ ( (x / n) % 3 ==1 ) && ( (y / n) % 3 ==1 )

 

   - 두 규칙
     ( x % 3 ==1 ) && ( y % 3 ==1 )
     ( (x / n) % 3 ==1 ) && ( (y / n) % 3 ==1 ) 은 n=1인 경우에  같아짐

 

즉, 공백을 출력하는 조건은 다음과 같음

if ((x / n) % 3 == 1 && (y / n) % 3 == 1) {
		cout << ' ';
	}

단 위의 조건은 n=1일때 같아지는 것이기 때문에
이는 재귀함수로 계속 n / 3을 해주고, 재귀함수의 종료조건은 n=1이 되는 순간인 n / 3 == 0

n=1이지만, 공백 조건에 해당하지 않은 경우는
공백 자리가 아니므로 ★을 출력!!

#include <iostream>
using namespace std;

void star(int x, int y, int n)
{
	if ((x / n) % 3 == 1 && (y / n) % 3 == 1) {
		cout << ' ';
	}
	else
	{
		if (n / 3 == 0)
			cout << '*';
		else
			star(x, y, n / 3);
	}
}
int main() {
	int n;
	cin >> n;
	for (int x = 0; x < n; x++)
	{
		for (int y = 0; y < n; y++)
			star(x, y, n);
		cout << '\n';
	}
}

 

다시 말하지만, 정말 나에겐 너무 힘든 문제였다.
처음엔 분할 정복이 뭔지도 몰랐지만, 분할 정복을 검색 한 이후에도 9개로 나누는 건 알겠는데 그 다음은??? 이랬었다..
첫 날은 3시간 정도 고민하다가 도저히 안되겠어서 다음날인 오늘 다시 풀어봤는데도
알 것 같으면서 모르겠는 문제..ㅜㅜ
구글링해서 코드를 봤는데, 조건이 왜 이렇게 된 건지 파악하는게 힘들어서 결국 총 10시간은 걸린것 같다ㅋㅋ

앞으로 이것처럼 이해 안 가고 모르는 문제가있으면, 이렇게 시간을 미련하게 끄는 것이 아니라..
적당히 답을 찾아 보는 것이 더 효율적일 것 같다..ㅠ