백준 : : 2447번 별 찍기(재귀) - C++ 풀이

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

2447번: 별 찍기 - 10

#include <iostream>
using namespace std;
 
void makeStars(int i, int j , int n){
    if(i%3 == 1 && j%3 == 1){ // 종료조건
        cout << " ";
    }
    else{
        if(n >= 3) makeStars(i/3, j/3, n/3);
        else cout << "*";
    }
}
 
 
int main(void){
    int num;
    cin >> num;
 
    for(int i = 0; i < num ; i++){
        for(int j = 0 ; j < num ; j++){
            makeStars(i, j, num);
        }
        cout << endl;
    }
}
 
 

 

위 그림처럼 *이 채워지는 부분은 형광펜으로  표시했고 그렇지 않은 empty 부분은 칸을 비운 상태로 그림을 그려봤다.

나는 empty 부분의 타입을 두개로 나눌 수 있다고 생각했다. 

 

1. 파란색 체크 부분 : 3으로 나눈 나머지가 1이 나오는 부분

2. 빨간색 세모 부분 

1번 타입의 empty는 쉽게 파악이 가능하고 금방 구현할 수 있다. <-- 이 부분을 재귀 함수의 종료 조건문으로 설정했다.

 

 

(i, j, n)를 이용하여 empty인지 * 모양인지 확인하기

먼저 n = 3 일때는 empty 부분이 바로 확인 가능하다. 

(1, 1, 3)을 parameter로 받을때 i, j 값이 모두 3으로 나눴을때 1이기 때문에 종료 조건문에 들어가 empty를 찍게 된다.

 

n = 9 일때

3으로 나눴을때 1이 되는 수는 바로 계산이 가능하기 때문에 넘어가겠다.

위 그림에 나타낸 (i, j) = (3, 3), (3, 4), (3, 5) ... (5, 5) 일때 코드를 따라가보자.

n이 9 이기때문에 9번째 줄이 수행되고 makeStar 함수를 다시 호출하게 된다. 이때  3, 4, 5 모두 3으로 나누면 몫이 1이 되어 그 값을 함수의 parameter로 보내준다.  (n값도 3으로 나눈 값을 보내준다.)

i와 j 값이 모두 1이기 때문에 종료 조건문에 들어가 empty를 찍게 된다.

 

 

 

n이 27일때

위 그림에서 원으로 표시한 부분의 계산을 손필기로 작성해봤다.

빨간색 세모 empty 부분 연산의 핵심은,empty 부분 좌표값을 3으로 나눈 값의 몫은 3으로 나눴을때 나머지가 1이라는 것이다.

; 1, 4, 7, ...

 

 

 

며칠 동안 이 문제를 붙잡고 있었다....ㅠㅠ
논리적으로 생각 정리하는 연습, 재귀 함수에 더 익숙해지기...