과학

쉽고 재미있는 수학 문제) 계단을 올라가는 경우의 수.txt

아오 화나....

 

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

 

문제)

 

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

 

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

 

 

 

예) N=3일때

 

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

 

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

 

stair.png

 

 

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

 

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

 

 

 

 

 

 

 

 

 

 

 

혹시 풀었어??

 

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

 

Fibonacci Sequence, 피보나치 수열이란

 

FS.png

 

이처럼 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

 

 

 

 

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

 

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

 

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

 

 

 

22개의 댓글

2020.01.06

n이 4일때 5가지 방법이 있다는거지?

1
2020.01.06
2
2020.01.06
0
2020.01.06

백준온라인저지에 있어서 풀었던 문제네~~ 리컬시브, 다이나믹프로그래밍, 백트래킹 등 생각할게 많고 최적화도 많이 할 수 있는 문제라 아주 좋은 문제라 생각해

0
2020.01.06

다이나믹밖에 생각이안난다

0
2020.01.06

디피!

0
2020.01.06
0

이거 수능 모고 기출에서 봤는댕

0
2020.01.07

예전에 확통에서 이런 거 많이 풀었던 것 같은데ㅋㅋ

0
2020.01.07

일반항 구해야지

0
2020.01.08
@라볶이

그게 피보나치수열은 좀 빡세더라 특성방정식을 어떻게 하던데

0
2020.01.08
@라볶이

피보나치 n번째 수=(((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n)/sqrt(5)

 

0
2020.01.07

와! 피보나치!

0
2020.01.07

다이나믹 프로그래밍 문제임?

0
2020.01.07

이걸 계산하는 거보다 모두의 계단 하는게 더 빡침

0
2020.01.07

그래서 코딩은 왜 안보여줘?

0

예전에 수학 사설모의고사에서 거의 비슷한 문제 본적 있어서 그때 피보나치 수열로 풀었던거 생각났었는데 바로 밑에 나오네ㅋㅋ

0
2020.01.08

자연수의 분할로 많이 나오던 문제네

0
2020.01.08

어쨌든 O(n)임 ㅅㄱ

0
2020.01.08

백트랙으로 풀었던거네

0
번호 제목 글쓴이 추천 수 날짜
공지 [게임] 게임 연재, 게임 정보는 게임 연재 판을 이용 해주시기 바랍니다 91 overflow 5 2017.04.18
공지 [기타 지식] 후기, 리뷰, 감상문은 허용 하지 않습니다 overflow 2 2016.07.29
공지 [기타 지식] 글 작성 금지 항목들 overflow 2 2014.04.06
공지 [기타 지식] 연속적인 글과 제목에 대하여 28 overflow 2 2013.08.11
공지 [기타 지식] 읽을 거리 판 입니다. 44 애드립 2 2012.07.25
435 [과학] 민간인 수준에서 면역에 대한 이해 - 2 - 백신과 항체 13 케리만 11 1 일 전
434 [과학] 민간인 수준에서 면역에 대한 이해 - 1 - 면역이 일어나는 방식 15 케리만 29 4 일 전
433 [과학] 야매로 설명하는 고층 일기도 보는 법 8 마리괭이 5 8 일 전
432 [과학] 안경, 렌즈 그리고 눈에 대하여 - 2. 원시 30 년차검안학도 3 12 일 전
431 [과학] 안경, 렌즈 그리고 눈에 대하여 - 1. 근시, 그리고 마이너스 ... 67 년차검안학도 7 16 일 전
430 [과학] 안경, 렌즈 그리고 눈에 대하여 - 0. 검안사 18 년차검안학도 1 16 일 전
429 [과학] [희대의 의학사기 사건] "인보사"에 대해서 19 Cassiiopeia 7 22 일 전
428 [과학] [면역학] 바이러스 감염 에서의 PD-1의 관계에 대해 17 Cassiiopeia 12 22 일 전
427 [과학] 면역질환과 기생충의 상관관계에 대한 재밌는 이야기 40 알비놀 1 29 일 전
426 [과학] [의약] ▶ 백신이 안 나오는 이유 31 Cassiiopeia 31 2020.04.15
425 [과학] 바이러스에 대해서 19 몸이좋아지고싶다 6 2020.04.12
424 [과학] 코로나 19 (COVID-19) 약물 치료에 관한 전문가 권고안(key q... 5 주작무새 3 2020.03.29
423 [과학] '우한 폐렴' COVID19의 최신 전염경로 연구와 백신... 11 알비놀 21 2020.03.19
422 [과학] [번역] 괴짜 공돌이의 Q&A: 피자 새 5 NOMT 8 2020.02.24
421 [과학] 5년전에 이미 예견된 바이러스 23 늅늅하고운다 21 2020.02.21
420 [과학] 펌)코로나바이러스 감염증-19 유행 관련 최신 정보 및 개인적... 9 웃음주머니 10 2020.02.20
419 [과학] 오늘까지 신종코로나바이러스 a.k.a. 우한폐렴 feat. 질병관... 8 도인 5 2020.02.11
418 [과학] [번역] 괴짜 공돌이의 Q&A: 태양을 먹어보자 12 NOMT 6 2020.01.30
417 [과학] 보이저호 이야기. 21 깨우치다 9 2020.01.15
416 [과학] [번역] 괴짜 공돌이의 Q&A: 나이아가라 빨대 11 NOMT 8 2020.01.10
서버에 요청 중입니다. 잠시만 기다려 주십시오...