강의로 돌아가기
고수분들 혹시 알아내는 다른 방법이 있나요?(문제 푸는 강력한 힌트가 있습니다.)
저는
n = 1
[1]
result = 1
n = 2
[1,1]
[2]
result = 2
n = 3
[1,1,1]
[1,2]
[2,1]
result = 3
n = 4
[1,1,1,1]
[1,2,1]
[1,1,2]
[2,1,1]
[2,2]
result = 5
n = 5
[1,1,1,1,1]
[2,1,1,1]
[1,2,1,1]
[1,1,2,1]
[1,1,1,2]
[2,2,1]
[2,1,2]
[1,2,2]
result = 8
n = 6
[1,1,1,1,1,1]
[2,1,1,1,1]
[1,2,1,1,1]
[1,1,2,1,1]
[1,1,1,2,1]
[1,1,1,1,2]
[2,2,1,1]
[1,2,2,1]
[1,1,2,2]
[2,1,2,1]
[1,2,1,2]
[2,1,1,2]
[2,2,2]
result = 13
1,2,3,5,8,13
0,1,1,2,3,5,8,13
위를 직접 다해보고
% 1234567? 이거 저번에 피보나치수열 풀때 봤는데로
피보나치수열이란걸 눈치 챘는데..
다 적어보는 무식한 방법말고
피보니치수열인걸 알아 내는 방법이 따로 있을까요?
-
다른 분들은 어떻게 알아내셨는지 궁금합니다.
HyunSoo Park―2022.10.11 15:59
-
https://namu.wiki/w/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%20%EC%88%98%EC%97%B4 경우의 수 부분보면 증명이 있습니다
Spatzle―2023.01.06 13:20
1 개의 답변
1칸까지 뛰는 방법은 1가지, 2칸까지 뛰는 방법이 2가지인 것은 쉽게 알 수 있습니다.
이제 n칸까지 뛰는 방법은 다음과 같이 생각해 볼 수 있습니다.
- [n - 1]번째 칸에서 1칸을 뛰어서 n번째 칸에 도착했다.
- [n - 2]번째 칸에서 2칸을 뛰어서 n번째 칸에 도착했다.
첫 번째 방법은 마지막에 1칸을 뛰어서 도착했고, 두 번째 방법은 마지막에 2칸을 뛰어서 도착했기 때문에, 위 두가지 방법 중 서로 중복되는 경우는 없습니다.
따라서 n번째 칸으로 뛰는 방법의 수는 [n-1]번째 칸으로 뛰는 방법 수 + [n-2]번째 칸으로 뛰는 방법의 수가 되며, 이는 피보나치 수열과 동일합니다.
-
그럼 문제의 1칸 2칸이 피보나치수열의 힌트인거죠..?
HyunSoo Park―2022.10.13 15:46
-
힌트라기 보단 n번째 칸의 값을 구하려면 n-1, n-2번째 칸의 값을 더하면 된다는걸 알아내고 보니 피보나치와 같은거죠. 1칸, 2칸 또는 3칸까지 뛰는 경우에는 어떻게 구할지도 한번 생각해보세요.
IceBear―2022.10.13 17:41
-
피보나치의 수열의 값과 비교해보세용
김경태―2023.01.07 23:09
-
지린다
Zero―2023.03.23 23:36
-
점화식으로 생각해보니 금방 생각해낼수 있었어요!
joooonis―2023.03.28 01:47
-
3칸까지 뛰는 경우는 [n-1] [n-2] [n-3]의 경우를 합하면 되는 건가요?
Miller―2023.10.17 21:12
답변 쓰기