[BOJ 2447 / C++] 별 찍기-10

문제

규칙을 찾아서 별 찍기(재귀)

문제 페이지

키포인트

• 3과 9일 때의 패턴을 출력해보고 27일 때로 접근하면 쉽다.

• 패턴을 어떻게 규칙적으로 찍어낼 수 있을까 고민해야 한다.

코드

#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

void star(int i, int j, int N) {
	if ((i / N) % 3 == 1 && (j / N) % 3 == 1)  // i / N: 반복되는 패턴을 만들기 위함.
		cout << " ";
	else {
		if (N / 3 == 0)
			cout << "*";
		else
			star(i, j, N / 3);
	}
}


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 << endl;
	}

	return 0;
}

풀이

• 3일 경우 패턴 만들기

  • 패턴의 자리값을i와 j라 하자
  • 둘 다 3으로 나누었을 때의 나머지가 1이면 된다.
  • i와 j가 1인 곳

     if(i % 3 == 1 && j % 3 == 1)
       cout << " ";

    
    
    

• 9일 경우 패턴 만들기

  • 두 자리값을 N/3으로 나누었을 때의 몫이 1이면 된다.
  • i와 j가 3,4,5인 곳

    if (i / (N/3) == 1 && j / (N / 3) == 1)
      cout << " ";

    
    
    

• 27일 경우 패턴 만들기

  • i와 j가 <3, 4, 5>인 곳, <12, 13, 14>인 곳, <21, 22, 23>인 곳 [9일 때의 패턴 반복 구현 위해]

  • 위의 방식을 그대로 넣고 돌리면 패턴이 반복되지 않는다. ==> 몫이 1~3이 나오므로

  • 따라서, 몫이 1이 나오도록 해주어야 한다.

    int main() { // N이 27일 때 패턴 반복이 되는지 확인하기 위한 예시
    	int N;
    	cin >> N;
    
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < N; j++) {
    			if (i % 3 == 1 && j % 3 == 1)
    				cout << " ";
    			else if (i / (N/9) %3 == 1 && j / (N / 9)% 3 == 1)  // N이 27일 때 이 조건으로 실행해보면 패턴 반복이 찍히는 것을 볼 수 있다.
    				cout << " ";
    			else 
    					cout << "*";
    		}
    		cout << endl;
    	}
    
    	return 0;
    }

    
    
    

• 재귀로 바꾸기

  if (i / (N/9) %3 == 1 && j / (N / 9)% 3 == 1)  
  				cout << " ";

  • 위의 (N/9)부분을 N/3으로 바꾸어 재귀를 하면 된다. (재귀로 호출하는 부분에 N/3이라서 if문에는 N만 들어감)
  • 재귀로 만들면 별을 찍는 부분은?
    N = N/3이 되게 재귀적으로 들어가게 되므로 결국 N이 1로 변할 때, *을 찍게 된다.

    void star(int i, int j, int N) {
    	if ((i / N) % 3 == 1 && (j / N) % 3 == 1)  // i / N: 반복되는 패턴을 만들기 위함.
    		cout << " ";
    	else {
    		if (N / 3 == 0)  // N이 1이되면 1 / 3 == 0 만족
    			cout << "*";
    		else
    			star(i, j, N / 3);
    	}
    }

느낀점

다 풀어놓고 몫을 1로 만들기부분에서 끙끙댔다.

조금만 더 생각해보면 됐을 걸 아쉽다. (맨날 아쉬운 것 같기도...)

많이 풀다보면 척척 풀 수 있겠지