백준, BOJ, 17478번 C++ [CPP] **

나는 재귀가 아직도 헷갈린다.

이 문제를 분석하며 한 번 더 배워가자

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

17478번: 재귀함수가 뭔가요?

 

---

 

이 문제는 또 재귀다.

 

결과를 보고 과정을 생각해내는 것이다.

해보자.

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

 

이게 원문이고

 

첫 째줄을 보자.

0. 어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.

-> 단독으로 존재한다. 재귀함수에 포함 x

 

2의 입력이 들어왔을 때

1. 3번 함수가 실행되었다는 것을 알 수 있음.

    2 - 1 - 0 (0에서 종료)

2. 시작했을 땐 앞에 아무것도 없고 함수로 들어가면 ____가 한번 씩 늘어남.

2 지만 0개의 ____를 가지고 있음 함수로 들어갈수록 ____가 늘어남

 

3. 답변하였지로 함수를 종료함

 

4. 함수 종료는 0 - 1 - 2 순서대로 종료

 

func(2) 일 때 파란색

func(1) 일 때 주황색

func(0) 일 때 초록색

 

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

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

________"재귀함수가 뭔가요?"
________"재귀함수는 자기 자신을 호출하는 함수라네" 
________라고 답변하였지.

____라고 답변하였지.

라고 답변하였지.

 

#맞는 풀이

#include<iostream>

using namespace std;

void init() {
    ios::sync_with_stdio(0);
    cin.tie(0);
}
string s = "____";

void func(int n, int k) {
    string line = "";
    int val = k - n;
    while (val--) line += s;

    cout << line << "\"재귀함수가 뭔가요?\"\n";

    if (n == 0) {
        cout << line << "\"재귀함수는 자기 자신을 호출하는 함수라네\"\n";
        cout << line << "라고 답변하였지.\n";
        return;
    }

    cout << line << "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n";
    cout << line << "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n";
    cout << line << "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n";

    func(n - 1, k);
    cout << line << "라고 답변하였지.\n";
    return;
}

int main() {
    init();
    int k;
    cin >> k;
    cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";
    func(k, k);

}