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 사용

좋은 웹페이지 즐겨찾기