6. c언어 재귀함수 - 경우의 수

 [실습 1] 경우의 수가 2가지인 문제 해결

  위 그림에서 앞으로 나아가다가 각각의 길의 갈림길에서 왼쪽으로 가면 2점을 오른쪽으로 가면 3점을 받을 수 있다고 한다. 이 길들 중 어떤 길을 가도 좋으나 길의 끝에 도달하였을 때, 그 점수의 합이 7점이 되지 않는다면, 그 사람은 지금까지 합한 점수의 3배에 달하는 벌금을 내야하고, 7점이면 100원의 상금을 받는다고 한다.

 

[실습 1] 이 문제를 다음과 같이 2개의 재귀호출을 사용하여 구현할 수 있다.

#include  <iostream>
using namespace std; 
void rec(int n, int point) 
{ 
    if(n == 3) 
    {         
        if(point == 7) cout << "상금 100원을 받으세요 " << '\n'; 
        else cout << "벌금" << point*3 <<  "원을 내세요.\n" ; 
        return; 
    } 
    rec(n+1, point+2); 
    rec(n+1, point+3); 
} 

int main(){ 
    rec(0,0); 
    return 0; 
}

★ 경우의 수와 재귀함수의 갯수는 같습니다

------------------------------------------------------------------------------------------------

[ 문제6-1 ]  N자리 2진수 만들기 

 

정수 n을 입력받아 n자리 2진수를 출력하시오. 단, 재귀호출을 사용하여 작성하시오.

 

 ◈ 입력 형식

정수 n을 입력받는다. 

 

 ◈ 출력 형식

입력받은 n자리 2진수를 출력하시오.

 

 ◈ 입력과 출력의 예

입력의 예	출력의 예
3	000 001 010 011 100 101 110 111

 

※ 경우의 수와 재귀 함수의 갯수는 같습니다. 위 문제는 0인 경우와 1인 경우 2가지 입니다. 재귀함수2개를 써야합니다.

※ 또한 앞에 출력된 값(0, 1)을 저장해야 하기 때문에 1차원 배열이 필요합니다. 

 

---------------------------------------------------------------------------------------------

 

[ 문제6-2 ] 올바른 괄호 사용

다음과 같은 경우는 괄호가 올바로 사용된 경우이고,

()()         (()())        ((())())        ()()()()

 

다음과 같은 경우는 괄호가 잘못 사용된 경우이다.

())(             ()())(      (()))(()       ()())(()

 

세 쌍의 괄호가 올바로 사용된 경우는 아래와 같이 총 5가지의 경우가 있다.

((()))         (()())        (())()      ()(())      ()()()

 

 n이 주어질 때 n쌍의 괄호가 올바로 사용된 경우를 모두 출력하는 프로그램을 작성하시오.

 

◈ 입력 형식

첫 줄에 10이하의 자연수 n이 주어진다.

 

◈ 출력 형식

  첫 줄에 총 경우의 수를 출력한다. 다음 줄부터 한 줄에 하나씩 n쌍의 괄호가 올바로 사용된 경우를 모두 출력한다.

 

◈ 입력과 출력의 예

입력의 예	출력의 예
3	((())) (()()) (())() ()(()) ()()()

※ 경우의 수와 재귀함수의 갯수는 같습니다. '('와 ')' 경우의 수는 2가지 입니다. 재귀함수2개를 써야합니다. 또한 괄호는 '(', ')'가 한쌍(1번)이기 때문에 n=3이면 6번(n*2) 호출을 해야합니다.

 

※ n=3일때 총 6번 호출을 해야 합니다. 그러면 (((((( , ((((() , .......... )))))) 이렇게 모든 괄호가 출력이 됩니다.

 

※ 이 중에서 올바른 괄호만 출력해야 합니다. 쉽게 생각하면 '(' 여는괄호 3개 '(' 닫는괄호3개 이러면 올바른 괄호라고 생각합니다.  여는 괄호와 닫는 괄호의 갯수가 같으면 올바른 괄호일까요?

 

하지만 )))((( 이런 경우도 출력이 됩니다. 어떻게 해결해야 할까요? 아래 소스 참고

 

-------------------------------------------------------------------------------------

[ 문제6-1 소스보기 ]

 

#include <stdio.h>
void rec(int);
int n;
int data[20];
int main()
{
	scanf("%d", &n);
	rec(0);
	return 0;
}
void rec(int x)
{
	if(x == n)
	{
		for(int i=0;i<n;i++)
			printf("%d", data[i]);
		printf("\n");
		return;
	}
	
	data[x] = 0;
	rec(x+1);
	
	data[x] = 1;
	rec(x+1);
}

 

-------------------------------------------------------------------------------------

[ 문제6-2 소스보기 ]

★ cnt 변수에 여는 괄호일때는 +1을 닫는 괄호일때는 -1을 더해줍니다. 닫는 괄호와 여는 괄호의 갯수가 같다면 cnt변수는 0일 될것입니다. 또, 여는 괄호보다 닫는 괄호의 갯수가 많다면 올바른 괄호가 아니겠지요 그러면 cnt값은 음수가 됩니다. 아래 소스 참고하세요

#include <stdio.h>
void rec(int, int);
int n;
char data[30];
int main()
{
	scanf("%d", &n);
	rec(0, 0);
	return 0;
}
void rec(int x, int cnt)
{
	if(cnt < 0) return;
	if(x == n*2)
	{
		if(cnt == 0)
		{
			for(int i=0;i<n*2;i++)
				printf("%c", data[i]);
			printf("\n");
		}
		return;
	}
	
	
	data[x] = '(';
	rec(x+1, cnt+1);
	
	data[x] = ')';
	rec(x+1, cnt-1);
}