programmers- lv.2 (멀리 뛰기)

문제링크: 멀리 뛰기

✍🏻 Information

	content
언어	python
난이도	⭐️⭐️
풀이시간	18분
제출횟수	∞
인터넷검색유무	yes

🍒 My Code

• 처음 작성한 풀이

import math
def solution(n):
    answer = 0
    two,one = n//2,n%2
    while two>=0:
        answer+= math.factorial(two+one)//(math.factorial(two)*math.factorial(one))
        two,one = two-1,one+2
        #print(one,two,answer)
    return answer%1234567
    

• 질문하기에서 dp보고 갑자기 보인 규칙

def solution(n):
    jump=[0,1,2]
    for i in range(3,n+1):
        jump.append(jump[i-2]+jump[i-1])
    return jump[n]%1234567

💡 What I learned

• 처음에 %12334567 나눈걸 답으로 return하라는걸 못봐서 계속 런타임에러 떴었다;;
• math 모듈을 import하면 factorial을 사용할 수 있다.
• 좋다고 생각한 풀이

def jumpCase(num):
    a, b = 1, 2
    for i in range(2,num):
        a, b = b, a+b
    return b

-> 얘도 피보나치 수열 썼다(dp라고도 할 수 ㅇ)
-> a,b=0,1로 수정하면 num=1일 경우도 통과된다고 한다.

• 팩토리얼과 중복순열을 이용하면 시간효율 측면에서 더 좋다. 재귀함수 쓰면 런타임이 매우매우 늘어난다.