3Level 멀리뛰기

문제 링크

링크텍스트

< 문제 핵심 >

1. 규칙성을 찾기

   → dp[0] = 1

   → dp[1] = 2

   → dp[2] = dp[0]+dp[1] = 1+2 = 3

   → dp[3] = dp[1]+dp[2] = 2+3 = 5

   → dp[n-1] = dp[n-3]+dp[n-2] = ?!

< 문제 아이디어 >

• dp 사용

  → 2*n 타일링과 유사 ( 이 문제는 효율성 존재 )

< 코드 >

1. dp 사용

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

print(solution(1))

< 구현 방식 >

( 사용한 메소드, 라이브러리 등 원리 )

1. dp 사용

• dp = []를 생성

• 규칙성 찾기

  → dp[0] = 1

  → dp[1] = 2

  → dp[2] = dp[0]+dp[1] = 1+2 = 3

  → dp[3] = dp[1]+dp[2] = 2+3 = 5

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

• for문을 이용

  • 0,1 부분은 이미 넣어두었기 때문에 range(2,n)으로 범위 지정

  • 각 부분을 대입할수도 있지만 저는 append를 이용

    → dp.append(dp[n-3]+dp[n-2])

• n == 1일 경우 예외로 설정

  → 굳이 필요없지만 쓸데없이 돌아가는 코드를 없애기 위함

• dp[n-1] 리턴

  → 찾고자하는 n부분의 인덱스는 n-1이기 때문에

< 결과 >

1. dp 사용