[프로그래머스] 멀리뛰기 in python

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는(1칸, 1칸, 1칸, 1칸)(1칸, 2칸, 1칸)(1칸, 1칸, 2칸)(2칸, 1칸, 1칸)(2칸, 2칸)의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한 사항

• n은 1 이상, 2000 이하인 정수입니다.

풀이

계단이 1칸, n=1 일 때 (1) -> F(1) = 1

계단이 2칸, n=2 일 때 (1,1) , (2) -> F(2) =2

계단이 3칸, n=3 일 때 (1,1,1), (1,2), (2,1) -> F(3) = 3 = F(2) + F(1)

계단이 4칸, n=4 일 때 (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2) -> F(4) = 5 = F(3) + F(2)

계단이 5칸, n=5 일 때 (1,1,1,1,1), (1,1,1,2), (1,1,2,1), ( 1,2,1,1), (2,1,1,1), (2,2,1), (2,1,2), (1,2,2) -> F(5) = 8 = F(4) +F(3)

 

∴ 해당 문제는 피보나치 수와 동일하게 풀면 된다

다만 F(0)=0 인 것을 인식할 필요가 없기 때문에 피보나치 수 문제와 달리 항상 1부터 시작해야한다는 것을 염두하고 풀자

 

def solution(n):
    a,b = 1,2
    for i in range(1,n): #F(1)부터 존재하므로
    	a,b = b, a+b     #F(n-1) = F(n-2)+ F(n-3)
    return a%1234567

 

def solution(n):	
	fibonum=[1,2]
	for i in range(n-1):
		fibonum.append(fibonum[i]+fibonum[i+1]) #F(n) = F(n-1) + F(n-2)
	return fibonum[n-1]%1234567                 #인덱스는 0부터 시작하므로

+ 나는 n이 주어지면 1,2로 중복으로 가져와서 그 합을 만든 다음 그 경우의 수를 찾고싶었다

나중에 위의 방법으로 해봐야지