아오 화나....

 

글쓴거 실수로 다날려먹었더니 다시써야하는데 너무 귀찮다... 그래도 이왕했던거 다시쓸께 ㅠㅠ

 

문제)

 

한번에 한칸 또는 두칸밖에 계단을 못올라간다고 할때

 

N개의 계단을 올라가는 경우의 수는 무엇일까?

 

 

 

예) N=3일때

 

(한번에 한칸씩 3번) 또는 (한번에 한칸올라간뒤 한번에 두칸) 또는 (한번에 두칸 올라간뒤 한번에 한칸) 이렇게 세가지의 방법이 있지

 

N=5이면은 이렇게 5개의 방법이 있어.

 

 

 

그렇다면 N개의 계단을 올라가는 경우의 수는 어떻게 구할까????????

 

개붕이들도 한번 생각해봐 ㅎㅎㅎ

 

 

 

 

 

 

 

 

 

 

 

혹시 풀었어??

 

풀기 힘들다면 힌트를 줄게.

 

Fibonacci Sequence, 피보나치 수열이란

 

 

이처럼 1, 1, 2, 3, 5, 8, 13.... 이 수열을 나타내는거야.

 

이수열은 어떠한 특징을 가지고 있을까?

 

바로 n번째 숫자는 n-1번째 숫자와 n-2번째 숫자의 합이야.

 

즉 4번째 숫자는 3번째 숫자(2) 와 2번째 숫자(1)의 합인 3인거지.

 

이문제는 피보나치 수열과 관련이 있어.

 

계단

n=1일때 경우의 수는 1   [ 1 ] 

n=2일때 경우의 수는 2   [(1 , 1), (2)]

n=3일때 경우의 수는 3   [(1 , 1, 1), (1, 2), (2, 1)]

n=4일때 경우의수는  5   [(1 , 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2)]

 

이처럼 n 번째 경우의 수는 n-1번째 경우의 수 + n-2번째 경우의 수와 같지.

 

왜 이렇게 되는걸까??

 

우리 개붕이들도 생각해볼시간을 더 줄께!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

알았어??? 똑똑한 개붕이들은 별로 안걸렸을수도 있지만 나는 답을 알아내는데 꽤 오래걸렸었어ㅠ

 

그럼 정답을 알아보자.

 

증명) N개의 계단을 올라가는 경우의 수는 몇개일까?

 

일단 계단을 한칸 내려보자

 

N-1개의 계단을 올라간다 가정해.

 

그렇다면 이 N-1개의 계단을 올라간후 마지막 N번째 계단을 올라가는 방법은? 

 

딱하나, 한칸 그냥 올라가는거 밖에없지.

 

그러므로 N-1번째 계단을 올라가는 방법을 통해, 즉 N-1번째 계단을 무조건 밟는다고 했을때, N개의 계단을 올라가는 경우의 수 는

 

N-1개의 계단을 올라가는 경우의 수 와 동일해

 

 

 

예를들어 N = 3이라고 해

 

그렇다면 N-1 =2 개의 계단을 올라가는 경우의 수는 [(1,1), (2)] 인데 이방법으로 올라가는 경우의 수는

 

[(1,1,1),(2,1)]처럼 무조껀 마지막에 한칸올라가는경우로 정해져있으니 경우의 수가 같아

 

 

 

하지만 꼭 N-1번째 칸을 밟아야할까??

 

우리는 문제에서 한번에 한칸도 올라갈 수 있지만 두칸도 올라갈수 있지.

 

이번에는 무조껀 마지막 발자국을 두칸으로 정해보자.

 

그렇다면? 전과 동일한 방법으로 N-2개의 계단을 올라가는 경우의 수와 같아.

 

 

이외에 또다른 방법이 있을까??

없어. 왜냐하면 우리는 한번에 최대 두칸만 올라갈수있으니깐 ㅎㅎ

 

그러므로 N개의 계단을 올라가는 경우의 수 = N-2개의 계단을 올라가는 경우의 수(마지막에 무조껀 한칸) + N-1개의 계단을 경우의 수(마지막에 무조껀 두칸)

 

               N                          =                        N-2                           +                      N-1

 

 

 

 

아까 날려먹은 글이 너무 짜증나서

 

이번엔 설명을 좀 더 간단히 해봤는데 이해 안되는 부분있으면 댓글로 물어봐줘!

 

참고로 내 전공은 컴공이고 코딩문제 풀다가 본 문제야 ㅎㅎ