[백준]2447번 별찍기 10 - C/C++

https://www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

 

재귀적인 패턴으로 별을 찍어 보자. 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=3k이며, 이때 1 ≤ k < 8이다.

출력

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

---

반복문과 재귀를 사용하는 별찍기 문제이다. 반복문을 돌려 그 자리에 맞는 원소(* 혹은 공백)을 출력한다고 생각하면 된다. 좌표 ( i , j )가 있을 때 그 중간의 공간은 모두 공백이다. 재귀 함수의 원소로는 현재 원소를 확인하고 싶은 좌표 i,j와 num이 들어오게 된다. 이때 num은 함수가 다루고 있는 정사각형을 9등분 했을 때의 변의 길이다. 중간의 공간이 모두 공백이라는 것은 크게 3덩이로 나누어 보았을때 중간 덩이인데 이는 %3 으로 나누었을때 1 인 값으로 생각 할 수 있다. 여기서 무엇을 나눌 지 생각해보면 i/num 와 j/num의 나머지를 구하면 된다. 27*27 정사각형을 생각 했을 때  num=9 인 정사각형 이면 (9,9)~(17,17) 를 꼭짓점으로 가지는 정사각형 부분이 0 이 되어야 한다. 이 값들은

(i/num) -> (i/9) (i/9)%3 = 1

(j/num) -> (j/9) (j/9)%3 = 1 이 된다.

이렇게 더 작은 부분까지 생각하게 된다면 코드는 다음과 같다.

#include <iostream>

using namespace std;
int N,cnt=0;

void solve(int i,int j,int num) {
	if ((i/num)%3 == 1 && (j/num)%3 == 1) {
		cout << " ";
	}
	else {
		if (num / 3 == 0) {
			cout << "*";
		}
		else {
			solve(i, j, num / 3);
		}
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			solve(i, j, N/3);
		}
		cout << "\n";
	}
	return 0;
}

---

내일이 선형대수학 기말고사여서 쉬운 틀린 문제를 하나 풀 생각으로 별찍기 10 을 선정하였다. 별찍기가 어려우면 얼마나 어려울까라는 생각으로 문제를 풀어봤는데 구현이 잘 되지 않았다. 어떻게 개행과 별을 적절히 찍을 지 고민이 됐다. 그래도 쉽사리 생각이 나지 않아서 언제 내가 틀렸는지 확인해본 결과 5달 전인것으로 보아 저번 여름방학때 푼 문제인 것 같았다. 5개월 사이에 분할정복에는 큰 발전이 없었나보다. 결국 해법을 생각해내지 못해 구글링을 해서 풀었다. 내가 놓친 부분은 나는 main 함수에서 solve() 함수를 딱 한번만 호출하여 그 안에서 더 작은 문제로 나누어 size 가 1 일때 *혹은 공백을 출력하는 방법으로 문제를 풀려 했는데 적절한 풀이는 i,j 번째 출력을 solve(i,j)함수를 이용하여 출력을 하는 것과 재귀식을 구하는 것이 포인트였던 것 같다. 저번 포스팅 문제도 그렇고 점화식을 구하는 문제들에 내가 굉장히 약한 것 같다. 점화식을 구해서 푸는 문제들을 연습해 봐야겠다.