[백준 알고리즘] 2447 별 찍기 - 10

 재귀 

: 원래의 자리로 되돌아가거나 되돌아옴

다시 자신의 함수를 호출하는 것을 재귀 함수라고 생각하면 쉽다.

 

재귀 함수를 작성할 때 중요한 것이 2가지가 있다.

1. base case를 만들 것

2. 스택이 줄어들어야 할 것

 

문제:    

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

2447번: 별 찍기 - 10

풀이방법:    

key point : 한칸 한칸이 " "일지, "*"일지 판별해내야 한다!

 

우선 N = 3일 때 부터 생각해보자.

N =3

빈 칸은 (1,1)로 i%3 ==1이면서 j%3 ==1인 부분이다.

 

다음으로 N = 9일 때를 생각해보자.

N = 9

 

빨간 동그라미 부분과 핑크 동그라미 부분을 나눠서 생각해보자.

빨간 동그라미 부분에서는  i%3 ==1이면서 j%3 ==1인 경우이고,

핑크 동그라미 부분에서는  i/3%3 ==1이면서 j/3%3 ==1인 경우이다.

 

다음으로 N = 27일 때를 생각해보자.

N = 27

파란 동그라미 부분과 빨간 동그라미 부분과 핑크 동그라미 부분을 나눠서 생각해보자.

파란 동그라미 부분에서는  i%3 ==1이면서 j%3 ==1인 경우이고,

빨간 동그라미 부분에서는  i/3%3 ==1이면서 j/3%3 ==1인 경우이고,

핑크 동그라미 부분에서는  i/3/3%3 ==1이면서 j/3/3%3 ==1인 경우이다.

 

만약 재귀를 쓰지 않는다면 

for문 i,j

if(i%3 ==1 && j%3 ==1){

print " "

}else f(i/3%3 ==1 && j/3%3 ==1){

print " "

}else f(i/3/3%3 ==1 && j/3/3%3 ==1){

print " "

} ... 

else{

print "*"

}

-->  N=3^k이며, 이때 1 ≤ k < 8 라고 했으니까 이 과정을.. 3^k..... ㅎ... 아닌거 같죵 ?

 

그래서 재귀를 사용해야 한다..!

 

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

 

재귀함수 호출 부분)

star(i/3, j/3, N/3)이 다시 호출된다.

만약에 i % 3 == 1 && j % 3 == 1 이게 아니라면

이제 다음으로는 i/3%3 ==1 && j/3%3 ==1을 검사해야 한다.

그렇기 때문에 star의 다음 i, j 값은 i/3, j/3이다.

N이 3의 거듭제곱(3, 9, 27, ...) 이기 때문에 당연히 한단계 내려갈 때도 N-1이 아니라 N/3이 되겠죠..?

따라서 나머지는 star(i/3, j/3, N/3)으로 넘어간다. 

이 과정이 반복이 되면서 N=1이 될 때까지 " "의 케이스가 있는지 확인한다. 

 

ex) N= 27에서 (4,8)을 생각해보자.

star(4, 8, 27)이 메인에서 호출이 되면,

star(1,2,9) -> star(1,2,3) -> star(1,2,1) -> "*"출력

 

ex) N= 27에서 (10,11)을 생각해보자.

star(10,11, 27)이 메인에서 호출이 되면,

star(3,3,9) -> star(1,1,3) -> " "출력

 

작성한 코드는 다음과 같다.

#include <iostream>
using namespace std;

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

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

성공한 사진!    

 

MEMO

시험기간에 이게 뭐하는 건지,, 최근들어 제일 어려운 문제였다. 재귀는 학교에서 배울때도 알듯 모를듯 알듯 모른다. 그래도 열심히 규칙을 찾고 정리를 해보니까 이해가 되었다.