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

백준 연습

by 빙하둘리 2022. 9. 22. 00:21

728x90

17478번 재귀함수가 뭔가요?

문제 링크

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

예제 입력이 2일 때 출력)

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

예제 입력이 4일 때 출력)

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

분석을 해보자.

일단 단 한번만 등장하는 문장은

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

이 부분이니 이 부분은 main으로 빼주자.

int main(void) {
	int x;
	cin >> x;

	cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";
	//이하 asking하는 부분 설계
    //이하 answering하는 부분 설계
}

그리고 재귀함수를 설계하는데 규칙성을 찾아서 설계하자.

대체적으로 보면, <<"재귀함수가 뭔가요?">>로 시작하는 질문부와

<<라고 답변하였지.>> 로 끝나는 답변이 여러 번 반복된다.

횟수를 거듭할수록 질문부는 언더바(_)표시가 4개씩 늘어나고

답변부는 언더바 표시가 4개씩 줄어든다.

입력이 2라고 했을 때

질문부에서 <<"재귀함수가 뭔가요?" "잘 들어보게... ">>부분은 2번 나오고 <<"재귀함수가 뭔가요?">>만 나오는 부분은 1번 나온다.

답변부의 경우 "재귀함수는 자기 자신을 호출하는 함수라네"가 1번 나오고 <<"라고 답변하였지가">> 3(=2+1)번 나온다.

입력이 4라고 했을 때는

질문부에서 <<"재귀함수가 뭔가요?" "잘 들어보게... ">>부분은 3번 나오고 <<"재귀함수가 뭔가요?">>만 나오는 부분은 1번 나온다.

답변부의 경우 "재귀함수는 자기 자신을 호출하는 함수라네"가 1번 나오고 <<"라고 답변하였지">>가 5(=4+1)번 나온다.

여기서 일반화를 하자면,

답변부는 언더바는 4*입력 만큼 나오고 "재귀함수는 자기 자신을 호출하는 함수라네"

라는 문장이 나오므로 이것 또한 main 함수로 빼준다.

int main(void) {

...(중략)
//답변부 공통 부분 구성
	for (int i = 0; i < x; i++)
	{
		cout << "____"; // 언더바가 4*x만큼 찍힌다.
	}
	cout << "\"재귀함수는 자기 자신을 호출하는 함수라네\"\n";
...(중략)
}

일단 답변부 - answer함수부터 구성해보자.

answer함수는 언더바가 줄어드는데 입력 (x+1)회만큼 문장이 출력된다.

그러면 종단점을 어떻게 지정해줘야 할까?

anwser(int x){

if(

answer(3)->answer(2)->answer(1)->answer(0);

answer이 0이상이면 모두 문장과 언더바를 조건에 맞게 출력해준다. 언더바 개수는 인자에 비례한 것을 참고해서 조건문을 쓴다.

종료 조건으로는 answer함수의 인자가 0일 때는 종료한다. 그래서

answer(int x){

//언더바 출력 규칙

if(x==0)

return 0;

}

결국 if(x==0)에서 종료하게끔 return문을 넣어준다. 그런데 생각해보니 다른 조건에서는 재귀적으로 함수를 부르므로 return answer(x-1);을 해준다.

또한 엔터의 경우 맨 마지막(x=0인 조건)제외 출력되므로 엔터도 넣어준다.

따라서 answer함수는 다음과 같다.

int answer(int n) {
	
	for (int i = 0; i < n; i++)
	{
		cout << "____";
	}
	cout << "라고 답변하였지.";
	if (n > 0)
	{
		cout << "\n";
		return answer(n - 1);
	}
	else
		return 1;
}

ask함수는

언더바의 개수가 인자와 반비례한다. 그 규칙성을 찾아보면

언더바 줄어드는 것은 별찍기 파트에서 역으로 찍는 것을 생각해보면 된다.

// n=5일 때 0번
//n=4일 때 1번
//n=3일 때 2번
//n은 줄어드는 수로 하고, x는 기존 횟수로 한 관계식을 이용 (main 함수에서도 x는 기존 횟수)

- 고정인자와 가변인자 정해주기

//그러면 4*(x-n)만큼 언더바를 출력해준다.

ask 함수의 매개변수는 (int n, int x)

x=5로 고정된 값인데 n은 5,4,3,2,1,0으로 가변한다.

언더바 4개 묶음 "____"는 (x-n)만큼 반복문으로 출력해준다.

for(int k=0; k<(x-n); k++)
{
cout<<"____";
}

입력 x가 4면,

<<"재귀함수가 뭔가요?" "잘 들어보게...">> 부분이 4번 그리고 마지막으로 <<"재귀함수가 뭔가요?">>만 나오는 부분이 1번이므로 x=0에서 조금 다르게 출력하고 종료하게 해준다.

int ask(int n, int x) {

"재귀함수가 뭔가요?" // 공통 출력 부분
if(n>0)
 "잘 들어보게..."; // 추가 출력 부분
 return 재귀함수부른다;

else // n==0인 조건
 return 0;

}

추가적인 문장을 출력하는 부분(n>0)과 그렇지 않을 때(n=0일 때)를 종합하면 다음과 같은 코드가 있다.

int ask(int n, int x)
{
 //언더바 출력 생략

	if (n > 0)
	{
		for (int i = 0; i < x - n; i++)
			cout << "____";
		cout << "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n";
		for (int i = 0; i < x - n; i++)
			cout << "____";
		cout << "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n";
		for (int i = 0; i < x - n; i++)
			cout << "____";
		cout << "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n";
	
		return  ask(n - 1,x);
	}
	else
	{
		return 1;
	}
}

언더바 출력까지 정리하고 종합하면

int ask(int n, int x)
{
	// n=5일 때 0번
	//n=4일 때 1번 x-n만큼
	//n=3일 때 2번
	//n,x 관계식 이용
	for (int i = 0; i < x - n; i++)
		cout << "____";
	cout << "\"재귀함수가 뭔가요?\"\n"; // 역슬래쉬 "로 큰따옴표 출력
	//n이라면 n+1번 나오는 문장...
	//결국 0일 때 탈출하게끔 해줘야지 n=3 2 1 0 => n+1=4 


	//횟수 세보고 n과의 연관성 찾고
	//조건으로 제외해주기!
	//아래 문장들은 n번만해주고 0을 전달하면 출력 안해준다.(결국 종료.)
	if (n > 0)
	{
		for (int i = 0; i < x - n; i++)
			cout << "____";
		cout << "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n";
		for (int i = 0; i < x - n; i++)
			cout << "____";
		cout << "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n";
		for (int i = 0; i < x - n; i++)
			cout << "____";
		cout << "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n";
	
		return  ask(n - 1,x);
	}
	else
	{
		return 1;
	}
}

이렇게 쓰면 n>0일 때(가변인자가 0 이상일 때) recur(n-1,x);를 return하며 재귀적으로 함수를 부른다.

(x는 고정인자)

또한 n=0일 때를 else로 처리해서 종료하게끔 return문을 써준다.

ask(질문부)함수, anwer(답변부)함수, main 함수를 전체적으로 종합하면 다음과 같다.

#include <iostream>
using namespace std;

int ask(int n, int x)
{
	for (int i = 0; i < x - n; i++)
		cout << "____";
	cout << "\"재귀함수가 뭔가요?\"\n"; // 역슬래쉬 "로 큰따옴표 출력
	if (n > 0)
	{
		for (int i = 0; i < x - n; i++)
			cout << "____";
		cout << "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n";
		for (int i = 0; i < x - n; i++)
			cout << "____";
		cout << "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n";
		for (int i = 0; i < x - n; i++)
			cout << "____";
		cout << "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n";
	
		return  ask(n - 1,x);
	}
	else
	{
		return 1;
	}
}

int answer(int n) {
	
	for (int i = 0; i < n; i++)
	{
		cout << "____";
	}
	cout << "라고 답변하였지.";
	if (n > 0)
	{
		cout << "\n";
		return answer(n - 1);
	}
	else
		return 1;
}


int main(void) {
	int x;
	cin >> x;

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

	//이하 answer
	for (int i = 0; i < x; i++)
	{
		cout << "____";
	}
	cout << "\"재귀함수는 자기 자신을 호출하는 함수라네\"\n";
	answer(x); //_____________라고 답변하였지

}

재귀함수 호출 횟수에 알맞게 조건 지정해주려면)1,2,3, ... , n은 정수가 n개

0,1,2,3, ... , n은 정수가 n+1개가 되는 원리를 이용해서

n을 입력 또는 인자로 받는데, 재귀함수는 n부터 0까지 부르고 끝내야 된다 == n+1번을 불러야된다 하면 n==0일 때 return -종료; 하게끔 해준다.

728x90

'백준 연습' 카테고리의 다른 글

백준 11382번 꼬마 정민 문제(자료형 크기에 유의) (0)	2022.09.04
백준 새싹 배열 5597번 과제 안 내신 분 (0)	2022.09.04
백준 새싹 배열 2738번 행렬 덧셈 (0)	2022.09.04
백준 class1 1157 단어 공부 (0)	2022.08.22
2920번 음계 (블락 적절히 나누기!) (0)	2022.08.21