[Programmers] 멀리 뛰기 문제 풀이 (Python)

1. 문제 풀이

1칸 또는 2칸씩 갈 수 있을 때 n번째 칸에 도달하는 방법의 갯수를 구하는 것이다.

현재 i번째 칸에 있을 때 도달할 수 있는 방법의 수는 1칸 또는 2칸씩 갈 수 있으므로 i-1번째 칸에서 오거나 i-2번째 칸에서 오는 방법뿐이다. 따라서 dynamic programming을 이용하여 구하였다.

• $\text{dp[i] = dp[i-1] + dp[i-2]}$
  • $\text{if i = 1, dp[1] = 1}$
  • $\text{if i = 2, dp[2] = 2}$

비슷한 문제로 타일링 문제가 있다. 같이 풀어보는 것을 추천한다.

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