멀리 뛰기

210701

'''
https://programmers.co.kr/learn/courses/30/lessons/12914
멀리 뛰기
[풀이]
1. 이제는 너무 익숙한 파보나치 수열
2. 개별 시행에서 각 위치는 한 칸 전과 두 칸 전에서밖에 도달하지 못한다.
=> 따라서, 각 위치의 경우의 수는 한 칸 전과 두 칸 전에서의 경우의 수의 합이다.
'''
def solution(n):
    dp = [1, 1] + [0] * (n-1)
    for i in range(2, n+1):
        dp[i] += (dp[i-2] + dp[i-1]) % 1234567

    return dp[n]
'''
리스트를 안쓰고도 풀 수 있는 방법이 있다. => 이 방법이 더 좋은 방법
=> 왜? 메모리 공간을 변수 두개밖에 사용하지 않았기 때문 => 어차피 알아야 할 것은 가장 끝 자리
=> 전자는, 모든 경우의 수를 다 알야아 할 때 더 유용
파이썬의 장점 중 하나. 동시 대입! => tmp를 따로 할당할 필요가 없다는 것
def solution(n):
    a, b = 1, 1
    for i in range(2, n+1):
        a, b = b, (a+b) % 1234567
    return b
'''