Today I Learned

오늘은 dp문제를 파이썬으로 풀어봤다.

CT_멀리뛰기

https://velog.io/write?id=80b63c55-c627-4d0a-9e08-70674e68d485

문제

한번에 한칸, 2칸을 뛸 수 있다. n이 주어질 때 끝까지 도달할 수 있는 방법을 알아내서 1234567을 나눈 나머지를 return해라.
n=4 / result = 5
n=3 / result = 3

풀이과정

• 일단 규칙을 찾기 위해 아래와 같이 반복해서 적어보았다.

  1 : 1 : 1
  2 : 12 21 : 2
  3 : 111 12 21 : 3 (1 2)
  4 : 1111 / 211 121 112 / 22: 5 (1 3 1)
  5 : 11111 / 2111 1211 1121 1112 / 221 212 122 : 8 (1 4 3)
  6 : 111111 / 21111 12111 11211 11121 11112 / 2211 2121 2112 1221 1212 1122 / 222 : 13(1 5 6 1)
  7 : 1111111 / 211111 121111 112111 111211 111121 111112 / 22111 21211 21121 21112 12211 12121 12112 11221 11212 11122 / 2221 2212 2122 1222 : 21 (1 6 10 4)

• 가장 쉬운형태의 점화식인 An = A(n-1) + A(n-2) 모양이 나옴을 알 수 있다.

• dp 리스트를 초기화한다. 이때 dp = [0] * (n+1)으로 초기화하면 간단하게 가능하다.
  0,1번째 값을 넣고 for문으로 dp 식을 만들어 채운다.

• 반환할 때 % 1234567을 달아주고 반환하면 완료!

Python 코드

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