알고리즘

[C++] Boj 17478 재귀함수가 뭔가요?

(ꐦ •᷄ࡇ•᷅) 2025. 1. 9. 09:54

문제 링크

17478 재귀함수가 뭔가요?


접근

우선 어제 배웠던 3단계 방식을 토대로 차례대로 접근하였다.

  1. 함수 원형 설정
  2. base condition 설정
  3. 재귀 식 구현

1. 함수 원형 설정

출력만 하는 것이므로 void 형, 또 횟수를 받아야 할 것 같아서 매개변수를 int n으로 줬다.

void Solve(int n);

2. base condition 설정

 

함수가 어떤 조건에서 멈출지 생각해 보았는데, n을 1씩 증가시킬 때 n이 사용자가 입력한 수가 되면 "재귀 함수가 뭔가요?"에 대한 질문을 하고 거기서 함수를 다시 호출하지 않고 답변을 하는 것을 볼 수 있다. 따라서 n == N일 때, 답변하고 끝마무리까지 하고 return 하게끔 설정했다.

3. 재귀 식 구현

void Solve(int n)
{
	// 질문
    if (n == N)
    {
        // 대답
        // 마무리
        return;
    }
    // 어쩌구저쩌구
    Sovle(n+1)
    // 마무리
}

코드

#include <iostream>
using namespace std;

const string str[] =
{
    "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n",

    "\"재귀함수가 뭔가요?\"\n",
    "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n",
    "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n",
    "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n",
    "\"재귀함수는 자기 자신을 호출하는 함수라네\"\n",
    "라고 답변하였지.\n"
};

void Solve(int n);
string printUnderBar(int n);

int N;

void Solve(int n)
{
    cout << printUnderBar(n) + str[1];
    if (n == N)
    {
        cout << printUnderBar(n) + str[5];
        cout << printUnderBar(n) + str[6];
        return;
    }
    cout << printUnderBar(n) + str[2];
    cout << printUnderBar(n) + str[3];
    cout << printUnderBar(n) + str[4];
    Solve(n + 1);
    cout << printUnderBar(n) + str[6];
}

string printUnderBar(int n)
{
    string str = "";
    for (int i = 0; i < n; i++)
    {
        str += "____";
    }
    return str;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";
    Solve(0);

    return 0;
}

 

결과


의문점

재귀함수는 풀면 풀수록 정답을 맞혀도 이게 진짜 맞나? 라는 의문이 든다. 아마 절차지향 사고 방식을 탈피하지 못했기 때문이라 생각한다. 다른 사람의 코드를 많이 볼 필요가 있다고 생각해 바킹독님의 해설 코드를 봤다.

코드

// Authored by : cpprhtn
// Co-authored by : -
// http://boj.kr/67c805f6167e49bebd8c13e9b0df4493
#include <bits/stdc++.h>
using namespace std;
int N;
void _bar(const char* str, int stk){
  for (int j = 0; j < stk; ++j) cout << "____";
  cout << str;
}
void solve(int cnt){
  _bar("\"재귀함수가 뭔가요?\"\n", cnt);
  if (cnt == N) _bar("\"재귀함수는 자기 자신을 호출하는 함수라네\"\n", cnt);
  else{
    _bar("\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n", cnt);
    _bar("마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n", cnt);
    _bar("그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n", cnt);
    solve(cnt + 1);
  }
  _bar("라고 답변하였지.\n", cnt);
}
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> N;
  cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";
  solve(0);
}

 

나랑 비슷한데 조금 달랐다. 나는 재귀 함수는 무조건 return 해야 돼! 라는 생각에 사로잡혀 return을 하여 코드를 더 반복되게 만들었다. 하지만 if, else를 사용하여 재귀 호출을 하면 반복되는 코드를 조금 줄일 수 있다.

개선된 코드

#include <iostream>
using namespace std;

const string str[] =
{
    "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n",

    "\"재귀함수가 뭔가요?\"\n",
    "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n",
    "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n",
    "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n",
    "\"재귀함수는 자기 자신을 호출하는 함수라네\"\n",
    "라고 답변하였지.\n"
};

void Solve(int n);
string printUnderBar(int n);

int N;

void Solve(int n)
{
    cout << printUnderBar(n) + str[1];
    if (n == N)
    {
        cout << printUnderBar(n) + str[5];
    }
    else
    {
        cout << printUnderBar(n) + str[2];
        cout << printUnderBar(n) + str[3];
        cout << printUnderBar(n) + str[4];
        Solve(n + 1);
    }
    cout << printUnderBar(n) + str[6];
}

string printUnderBar(int n)
{
    string str = "";
    for (int i = 0; i < n; i++)
    {
        str += "____";
    }
    return str;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";
    Solve(0);

    return 0;
}

 

뭔가 더 깔끔해져서 찝찝했던 조금 기분이 나아졌다.