pushback

 재귀가 익숙하지 않으면 풀기 힘든 문제다. 근데 알고보면 별 거 없다.

 \(n = 3\)의 별 모양을 보자

 \(n = 9\)인 것을 보자

가운데 \(n = 3\)의 별 모양 하나가 빠진 모양이다.

\(n = 27\)인 것을 보자.

 가운데 \(n = 9\)의 별 모양 하나가 빠진 모양이다.

 끝났다. \(n = 3^k\)의 별 모양은 \(n = 3^{k - 1}\) 별 모양 하나가 가운데에 비어있는 모양이다.

 \(n = 3^k\)부터 \(n = 1\)까지 재귀적으로 별 모양을 그리면 원하는 별 모양을 얻을 수 있다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

char star[2201][2201] = { 0 , };

void recur(int x, int y, int cur)
{
	// n = 1이면 별 찍고 리턴
    if (cur == 1)
    {
        star[x][y] = '*';
        return;
    }
    
    int next = cur / 3;
	
    // 가운데 빼고 재귀로 돌기
    // 1 2 3
    // 4   6
    // 7 8 9
    // 항상 이렇게 이중 for문이 돈다.
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (i == 1 && j == 1) // 가운데는 스킵
                continue;
            else
                recur(x + (i * next), y + (j * next), next);
        }
    }		
}
int main()
{
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    // 모두 빈칸으로 초기화
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) star[i][j] = ' ';

    // 재귀 시작
    recur(0, 0, n);
	
    // 출력
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << star[i][j];
        }
        cout << '\n';
    }
	
    return 0;
}

팩토리얼 문제와 달리 이번 문제는 친절하게 점화식이 나왔다. 이를 이용해서 재귀로 작성해보자.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int fibo(int n) {
    if (n <= 1) return n;
    else return fibo(n - 1) + fibo(n - 2);
}

int main()
{
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
	
    cout << fibo(n);
	
    return 0;
}

 팩토리얼 문제는 나중에 나올 Dynamic Programming(= DP)로 푸는 것이 훨씬 효율적이지만, 문제가 속해있는 단계 자체가 재귀이고 \(n\)의 범위도 12까지이니 간단하게 재귀로 해결하자.

 재귀로 구현해야 할 것은 하나이다.

 어떤 자연수\(n\)이 있을 때, \(n! = n * (n - 1)!\)임은 자명하다.

 이것을 이용해서 재귀함수를 한번 작성해보면

이런 코드를 작성할 수 있다.

 물론 단순히 for문을 사용하여 팩토리얼을 구할 수도 있지만, 팩토리얼 같이 점화식이 존재한다면 재귀로 구할 수 있다는 점만 알고 넘어가자.

 점화식이 있는 문제에 대해선 나중에 나올 DP 파트에서 자세히 다뤄보겠다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int fact(int n) {
    if (n <= 1) return 1;
    else return n * fact(n - 1);
}

int main()
{
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
	
    cout << fact(n);
	
    return 0;
}