백준 17478

문제분석

n=2, 질문 3번, _개수(0, 4, 8)

n=4, 질문 5번, _개수(0, 4, 8, 12, 16)

즉, 수학적 귀납법으로 n=k 라면 질문의 개수는 k+1이고 최대 "_" 개수는 4k 

 

1. 함수정의

void func(int k, int cnt, int answer);

// K=2 일때 
void func(2, 4 * 2, 2+1);

k는 재귀횟수, cnt는 "_" 개수, answer은 질문의 개수이다.

 

2. Base conditon

if (answer == 1){
    cout << "문장출력";
    return;
}

재귀함수가 종료되는 조건은 k+1, k, k -1 ... 번 질문을 하다가 질문이 1번 남았을 때 

 

3. 재귀식

n=1 일때 func(n, 4n, n+1) 가정해보자 

• func(1, 4, 2) 호출 후 Base 조건 성립 X 
• 다음 질문이 있는지 체크 : func(1, 4n-4, n-1) -> func(1, 0, 1) 호출 
• Base 조건이 성립한다. 즉, 마지막 질문(질문이 끝남)이므로 문장 출력 후 재귀함수 종료
• func(1, 0, 1) 함수는 스택 프레임에서 제거되고 func(1, 4, 2)의 함수를 계속 실행
• 질문이 모두 종료됬으므로 종결 문장 출력후 "라고 답변하였지." 문장을 재귀함수로 실행

 

n=2 일때 func(n, 4n, n+1) 가정해보자

• func(2, 8, 3) 호출 후 Base 조건 성립 X 
• 다음 질문이 있는지 체크 : func(2, 4n-4, n-1) -> 첫번째 함수인 func(2, 4, 2) 호출
• Base 조건 성립 X, 다음 질문이 있는지 체크 -> 두번째 함수인 func(2, 0, 1) 호출
• Base 조건 성립한다. 즉, 질문이 끝났으므로 문장 출력 후 재귀함수 종료
• 두번째 함수인 func(2, 0, 1) 스택 프레임에서 제거되고 func(2, 4, 2) 함수를 계속 실행
• func(2, 4, 2) 함수의 질문을 출력 후 스택 프레임에서 제거 후 최초 재귀함수 func(2, 8, 3) 호출
• 최초 재귀함수이기 때문에 종결 문장을 출력 후 "라고 답변하였지." 문장을 재귀함수로 실행

 

코드

#include<iostream>	
using namespace std;

void func2(int cnt, int answer) {
	if (answer == 1) {
		cout << "라고 답변하였지." << '\n';
		return;
	}

	for (int i = 0; i < cnt; i++) cout << '_';
	cout << "라고 답변하였지." << '\n';
	func2(cnt - 4, answer - 1);
}

void func(int k, int cnt, int answer) {
	if (answer == 1) {
		cout << "\"재귀함수가 뭔가요?\"" << '\n';
		cout << "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어." << '\n';
		cout << "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지." << '\n';
		cout << "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"" << '\n';
		return;
	}

	func(k, cnt - 4, answer - 1);
	for (int i = 0; i < cnt; i++) cout << '_';
	cout << "\"재귀함수가 뭔가요?\"" << '\n';
	for (int i = 0; i < cnt; i++) cout << '_';

	if (k + 1 == answer) {
		cout << "\"재귀함수는 자기 자신을 호출하는 함수라네\"" << '\n';
		// "라고 답변하였지." 재귀함수 호출 
		func2(cnt, answer);
	}
	else {
		cout << "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어." << '\n';
		for (int i = 0; i < cnt; i++) cout << '_';
		cout << "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지." << '\n';
		for (int i = 0; i < cnt; i++) cout << '_';
		cout << "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"" << '\n';
	}
}


int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	// 1.입력
	int N;
	cin >> N;

	cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다." << '\n';
	func(N, 4 * N, N + 1);



	return 0;
}