이 문제 빨리 풀어주세요 급해요

이 문제 빨리 풀어주세요 급해요

작성일 2024.05.06댓글 2건
    게시물 수정 , 삭제는 로그인 필요

profile_image 익명 작성일 -

.

profile_image 익명 작성일 -

이건 점화식 문제이군요,

만약 n개의 개단이 있다고 하고, 계단을 오르는 방법이 1,2칸씩 오르는 방법이 있다고하면

계단이 1개있다고 하면 f(1) 이죠, 올라가는방법은 1가지입니다, 한칸씩올라가는방법

계단이 2개있으면 f(2)이죠 올라가는 방법은 총 2가지입니다. 1 + 1 ,과 2 죠

계단이 3개있다고하면 f(3) 인데, 올라가는방법은 1로쭉가는방법 1가지, 1과 2 를섞어올라가는방법 2가지 (2C1) 합쳐서 3가지입니다.

설명하자면 3칸일때 1칸만 사용하는 방법 1가지, 그리고 2칸,1칸 두가지 방법중 순서를 결정하는 경우의수 ( 2콤비네이션1) 이렇게 입니다

근데 규칙을 찾아보면 신기하게도,

f(1) + f(2) = f(1+2) 입니다.

왜냐하면, 제가 n개의 개단을 올랐다고 가정했을때,

n+2번째 계단을 올라가는 방법은

n번째 계단에서 2칸을 뛰어 한번에 올라가는방법과,

n+1번째 계단에서 1칸을 뛰어 올라가는 방법이 있기떄문이죠,

즉 관계는

f(n) + f(n+1) = f(n+2) 입니다.