[정답] 계단을 올라갈 때 정보
[정답] 계단을 올라갈 때
본문
피보나치 수열의 원리를 알고 있는지에 대한 문제였습니다.
피보나치 수열이 뭔지는 아시죠?
an=an-1 + an-2
5개짜리 계단을 올라가는 방법의 수 = 3개짜리 계단을 올라가는 방법의 수 + 4개짜리 계단을 올라가는 방법의 수
위와 같이 됩니다.
왜냐면 5개짜리 계단을 올라가기 직전에는 3번째 계단에 있거나, 4번째 계단에 있기 때문입니다.
3번째 계단까지 x가지 방법으로 왔다면 3번째 계단에서 2계단을 오르면 5번째 계단에 오게 됩니다. 그러니 5번째 계단을 오기 직전에 밟은 계단이 3번째 계단인 경우는 x가지가 됩니다.
마찬가지로 4번째 계단을 오는 방법이 y가지라면 4번째 계단에서 1계단을 더 올라 5번째 계단에 오르는 방법의 수는 y가지가 됩니다.
그러므로 5개의 계단을 오를 수 있는 방법의 수는 x+y 가지가 됩니다.
위 원리를 이해하면 피보나치 수열을 이용해 쉽게 풀 수 있습니다.
a1=1
a2=2
a3=1+2=3
a4=2+3=5
a5=3+5=8
a6=5+8=13
a7=8+13=21
a8=13+21=34
a9=21+34=55
a10=34+55=89
피보나치 수열이 뭔지는 아시죠?
an=an-1 + an-2
5개짜리 계단을 올라가는 방법의 수 = 3개짜리 계단을 올라가는 방법의 수 + 4개짜리 계단을 올라가는 방법의 수
위와 같이 됩니다.
왜냐면 5개짜리 계단을 올라가기 직전에는 3번째 계단에 있거나, 4번째 계단에 있기 때문입니다.
3번째 계단까지 x가지 방법으로 왔다면 3번째 계단에서 2계단을 오르면 5번째 계단에 오게 됩니다. 그러니 5번째 계단을 오기 직전에 밟은 계단이 3번째 계단인 경우는 x가지가 됩니다.
마찬가지로 4번째 계단을 오는 방법이 y가지라면 4번째 계단에서 1계단을 더 올라 5번째 계단에 오르는 방법의 수는 y가지가 됩니다.
그러므로 5개의 계단을 오를 수 있는 방법의 수는 x+y 가지가 됩니다.
위 원리를 이해하면 피보나치 수열을 이용해 쉽게 풀 수 있습니다.
a1=1
a2=2
a3=1+2=3
a4=2+3=5
a5=3+5=8
a6=5+8=13
a7=8+13=21
a8=13+21=34
a9=21+34=55
a10=34+55=89
댓글 0개