[백준][C++] 17478번 재귀함수가 뭔가요?

재귀함수가 뭔가요?

문제 링크

재귀함수가 뭔가요?

분석

재귀 호출의 진행과 복귀 과정을 특정 문자열 출력으로 표현하는 문제입니다.

재귀 함수의 반복 횟수는 입력으로 횟수가 주어집니다.

출력해야하는 문자열은 크게 다음과 같은 종류로 나뉩니다.

• 재귀 함수를 시작하기 전에 출력되는 문자열
• 재귀 함수가 호출되며 반복적으로 출력되는 문자열
• 재귀 함수의 탈출 조건이 성립했을 때 출력되는 문자열
• 재귀 함수의 스택이 해제되며 출력되는 문자열

재귀 함수가 호출되거나 스택이 해제되며 출력 될 때에는, 출력 횟수에 따라 "____"가 문자열 앞에 먼저 출력되어야 합니다.

풀이

#include <iostream>
#include <string>

void PrintRecursionFunc(int MaxCount, int CurrentCount)
{
    if (CurrentCount > MaxCount)
    {
        return;
    }
    
    std::string Underbar;

    int UnderbarCount = (CurrentCount) * 4;
    for (int i = 0; i < UnderbarCount; ++i)
    {
        Underbar += '_';
    }

    std::cout << Underbar << "\"재귀함수가 뭔가요?\"" << std::endl;

    if (CurrentCount == MaxCount)
    {
        std::cout << Underbar << "\"재귀함수는 자기 자신을 호출하는 함수라네\"" << std::endl;
    }
    else
    {
        std::cout << Underbar << "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어." << std::endl;
        std::cout << Underbar << "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지." << std::endl;
        std::cout << Underbar << "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"" << std::endl;
    }

    PrintRecursionFunc(MaxCount, CurrentCount + 1);

    std::cout << Underbar << "라고 답변하였지." << std::endl;

}

int main()
{
    int MaxCount = 0;
    std::cin >> MaxCount;

    std::cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다." << std::endl;

    PrintRecursionFunc(MaxCount, 0);

    return 0;
}

성능 요약

시간 복잡도는 $O(n^{2})$입니다.

• 재귀 함수 호출 $O(n)$
• 언더바를 생성하는 반복문 $O(n)$
• $O(n) \times O(n)$

공간 복잡도는 $O(n)$입니다.

• 재귀 함수 호출 스택 $O(n)$

메모리: 2020 KB

시간: 4 ms