멀리 뛰기 (Python)

문제

프로그래머스

---

 

문제 풀이

---

전형적인 다이나믹 프로그래밍의 문제로 점화식만 잘 세우면 쉽게 문제를 풀 수 있다.

어떤 순서의 모든 경우의 수는

1) 직전의 결과에 1을 더하고

2) 직전의 직전의 결과에 2를 더하는 결과를 합치면 경우의 수가 완성이 된다.

 

그러므로 점화식은 

dp[n] = dp[n-1] + dp[n-2] 

가 된다.

n 이 1일때와 2일 때의 경우는 쉽게 알 수 있으므로 미리 초기값으로 설정하고 점화식을 반복한다.

 

코드

---

 

 

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