문제
접근
DP문제이다.
접근법은 타일링문제와 똑같다.
n칸의 경우의 수는 n-1칸에서 1칸으로 뛰는 방법 + n-2에서 두칸으로 뛰는방법이다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
def solution(n):
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
dp[i] = (dp[i-1] + dp[i-2])%1234567
return dp[n]