[정보올림피아드 대비]16. 점화식(재귀 포함)을 이용한 문제

점화식이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타내는 관계식이다. 즉, 수열 { an }의 각 항 an 이 함수 f를 이용해서 f(an) = an+1 과 같이 귀납적으로 정의 될때 f를 수열 {an}의 점화식이라고 하며 또한 수열 {an}은 점화식 f로 정의 된다고 한다. 예) 하노이의 탑 유명한 하노이이탑 문제는 n개의 원판을 이동하는 회수를 수열 an으로 정의 하면 n개의 원판을 이동시키기 위해서는 그 위쪽 n-1개의 원판을 다른 막대로 이동한 후, 맨 아래쪽 원판을 이동하고 다시 n-1개의 원판을 이동해야 하므로 다음과 같은 점화식이 성립함을 알수 있다. f(n) = f(n-1) + 1 + f(n-1) = 2*f(n-1) + 1 = 2^n - 1 (단, f(1)=1) 예) 피보나치수열의 경우 1항은 1,2항은 1 이고 3항 부터는 전항 + 전전항 이므로 f(n) = f(n-1) + f(n-2) (단, f(1) =1,f(2)=1) 예) 자연수 수열 : 1,2,3,4,.... f(n) = f(n-1) + 1 (단 f(1) = 1)

1. 평면위에서 5개 직선으로 원의 내부를 최대 몇부분으로 나눌 수 있을까요? 만약 평면 위에서 100개 직선으로 원의 내부를 최대 몇 부분으로 나눌 수 있을까요?

문제풀이)

그림을 보면

직선 1개로 나누는 경우 : 2개

직선 2개로 나누는 경우 : 4개

직선 3개로 나누는 경우 : 7개

직선 4개로 나누는 경우 : 11개

직선 5개로 나누는 경우 : 16개

...

이렇게 확인을 해 보면

f(1) = 2

f(n) = f(n-1) + n

인 것을 확인 할 수 있습니다.

따라서 f(n) = 2 + 2 + 3 + 4 + 5 + .... + n 이 되는 것을 확인 할 수 있습니다.

 

이렇게 확인을 하면 1부터 n까지의 등차수열의 합 + 1 의 값이 되는 것을 확인이 되므로 

1부터 100까지의 합 = 5050 + 1

5051  

2. 평면 위의 10개 원이 서로 만난다면 평면을 최대 몇개의 구역으로 나눌 수 있을까요?

또한 평면 위에서 원 2011개는 평면을 몇개의 구역으로 나눌 수 있을까요?

문제풀이)

그림을 보면

원이 1개일때 2개 구간으로 나눌 수 있습니다.

2개일때 4개 구간으로 나눌 수 있습니다.

3개일때 8개 구간으로 나눌 수 있습니다.

4개일때 14개 구간으로 나눌 수 있습니다.

 

증가 되는 규칙을 살펴 보면 2,4,6,8... 과 같이 증가 되는 규칙을 찾을 수 있습니다.

따라서 다음과 같은 점화식을 유도할 수 있습니다.

f(n) = f(n-1) + 2 * (n-1) (단 f(0) = 0,f(1)=2)

 

3. 계단을 오를때 한번에 한계단 혹은 두계단만 오를 수 있다고 한다. 이 때 4 계단을 올라가는 방법의 수를 구하시오. 그리고 10계단을 올라가는 경우의 수를 구하시오.

문제풀이)

0계단을 올라가는 경우는 1가지(아무것도 올라가지 않는 경우)

1계단을 올라가는 경우는 1가지(0계단에서 1계단 올라오는 경우만 존재)

2계단을 올라가는 경우는 2가지(0계단에서 2계단 올라오는 경우 와 1계단에서 1계단 올라 오는 경우)

3계단 올라 오는 경우는 3가지(2계단에서 1계단 올라오는 경우와 1계단에서 2계단 올라 오는 경우)

따라서 n 계단을 올라오는 경우의 수를 계산하면

f(n) = f(n-1) + f(n-2) (단 f(0) = 1,f(1)=1)

따라서 피보나치 수열이다.

표를 그려 보면 다음과 같이 그려 볼 수 있다.

 

0	1	2	3	4	5	6	7	8	9	10
1	1	2	3	5	8	13	21	34	55	89

따라서 10계단 올라가는 경우의 수는 89 가지

 

 

 

 

 

 

 

 

 

[역대 기출문제]

https://docs.google.com/forms/u/0/d/e/1FAIpQLSfeUSKhG8a7IzQ-_TgTBdo5zxq_ALRX4DMQ8HMZJXUpaXctfw/viewform

17-1. 점화식(재귀 포함)을 이용한 문제(초등부)

https://docs.google.com/forms/d/e/1FAIpQLSfTjLQWwmXh3WKbTzOB0qIgkY7Ar5Q_XLFO-k3wSbvzKgxP5w/viewform

17-2. 점화식(재귀 포함)을 이용한 문제(중등부)

https://docs.google.com/forms/d/e/1FAIpQLSdO7W8PCn7eEW2nEoPWjWq1t5fohcLoUT5-e-2wX623_kDjBQ/viewform

17-3. 점화식(재귀 포함)을 이용한 문제(중고등부)