문제 설명
효진이는 멀리 뛰기를 연습하고 있습니다.
효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다.
칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다.
멀리뛰기에 사용될 칸의 수 n이 주어질 때,
효진이가 끝에 도달하는 방법이 몇 가지인지 알아내,
여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요.
제한 사항
n은 1 이상, 2000 이하인 정수입니다.
먼저 n이 1일 때 부터 5일 때까지 결과값이 무엇인지 계산해보았다!
(규칙을 찾기 위함) (n=5 정도는 손으로 할 수 있으니까..)
(게다가 n이 3이랑 4일때도 예시로 주어졌다.)
n=1 -> 1
n=2 -> 2
n=3 -> 3
n=4 -> 5
n=5 -> 8
...
그 결과...
n이 주어질 때 결과값은 n-1 과 n-2의 결과값의 합이라는 규칙을 발견하였다!
(포스팅 후에 어떻게 이런 규칙이 나오게 되었는지 생각해볼 예정이다.)
순간 무언가 내 머릿속을 스쳐갔다.
이거.. 어디서 많이 본 규칙인데..?
피보나치 수열!!!
알고리즘 초보인 나도 피보나치 수열이 생각났다니.. (그래도 나름 이과다)
그래서 바로 적용해보았다.
def solution(n):
a,b = 1,2
if n==1:
return 1
elif n==2:
return 2
for i in range(1,n):
a,b = b, a+b
return a%1234567기존의 피보나치 수열이랑은 시작이 다르기 때문에
문제에 맞게 a, b값을 바꿔주었고,
n=1 일때와 n=2 일때의 예외도 생각했다.
그 후 반복문인 for문을 이용해서 원하는 결과를 얻을 수 있었다.
LV2 문제이지만.. 초보인 나는 문제를 풀었다는 사실에
매우 기쁘지 않을 수 없었다.
알고리즘 공부, 열심히 해야겠다.
-끝-
