강의로 돌아가기
고수분들 혹시 알아내는 다른 방법이 있나요?(문제 푸는 강력한 힌트가 있습니다.)
저는
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
2 개의 답변
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
[같은 것이 있는 순열]
- 1칸 이동 칸수 + 2칸 이동 칸수 = n 즉, x+2y = n
n=6일때, 계산식은 x+2y = 6
x : 6 => y : 0 -----------> (6,0)
x : 5 => 성립 불가
x : 4 => y : 1 -----------> (4,1)
x : 3 => 성립 불가
x : 2 => y : 2 -----------> (2,2)
x : 1 => 성립불가
x : 0 => y : 3 -----------> (0,3)
x축 : 6, 4, 2, 0 ----즉-----> x = for(let i=0; i<Math.floor(n / 2)+1; i++) ( n-2i )
y축 : 0, 1, 2, 3 ----즉-----> y = for(let i=0; i<Math.floor(n / 2)+1; i++) ( i )
- 이러한 식으로 입력값 n에 대한 이동 가능한 최대 횟수를 얻을 수 있음
- '같은 것이 있는 순열' 계산식을 활용하여 경우의 수 계산( i는 팩토리얼 )
- 경우의 수 계산식 : (x+y)! / x! * y! -----> x! + x! / x! * y! -----> x! / yi
n 이 6일때,
(x이동 횟수, y이동 횟수) = 경우의 수 ------------> (6,0) = 1, (4,1) = 5, (2,2)=6, (0,3)=1
경우의 수 총합 : 13
이런식으로 n=1~6까지만해도 피보나치 연걸 확인 가능합니다.
※ 저는 제가 적은 대로 풀이하다가 팩토리얼 때문에 숫자가 터져서 피보나치로 고치러 갑니다...ㅜ