[프로그래머스] 멀리 뛰기 (Python)

문제 링크

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

프로그래머스

 

문제 설명

효진이는 멀리 뛰기를 연습하고 있는데, 한 번에 1칸, 또는 2칸을 뛸 수 있다. 

멀리 뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇가지인지 알아내 여기에 1234567을 나눈 나머지를 리턴하는 함수를 완성하시오.

제한사항

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

 

풀이

dp 문제이다. 예를 들어 n이 4인 경우 (1, 1, 1, 1), (1, 2, 1), (1, 1, 2), (2, 1, 1), (2, 2) 총 5가지 방법으로 끝에 도달할 수 있게 된다.

 

n = 1일 때의 방법은 1 => (1)

n = 2일 때의 방법은 2 => (1, 1), (2)

n = 3일 때의 방법은 3 => (1, 1, 1), (1, 2), (2, 1)

n = 4일 때의 방법은 5가 된다. => (1, 1, 1, 1), (1, 2, 1), (1, 1, 2), (2, 1, 1), (2, 2)

 

이것을 토대로 점화식을 찾아보면, n이 3이상일 때의 점화식은

 

가 된다.

 

✅ Code - 성공

def solution(n):
    
    if n < 3:
        return n
    
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    
    for i in range(3, n + 1):
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567 

    return dp[n]