[백준] 2775 - 재귀함수로 풀어보자

문제: www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

 

 

표를 그려서 문제를 파악해보자.

 

1
1
1
1
1
1	6
1	5	15
1	4	10	20	35	56
1	3	6	10	15	21	28	36	45
1	2	3	4	5	6	7	8	9	...

 

(a층 b호의 숫자) = (a층 b-1호의 숫자) + (a-1층 b호의 숫자) 라는 것을 알 수 있다.

 

이때 수열이 자기 자신의 항들로 정의되어 있는데

 

이를 두고 수열이 귀납적 또는 재귀적으로 정의되어 있다고 한다.

 

따라서 재귀함수를 이용하는게 가장 쉽고 편하다.

 

주의: 이 문제에서는 입력값이 작아서 괜찮지만, 재귀함수는 기본적으로
스택오버플로우의 위험을 항상 가지고 있다. 그래서 보통 재귀함수는 동적 계획법과 함께 쓰인다.

 

위의 점화식과, 주어진 초기값의 조건을 사용해서 함수를 정의한다.