프로그래머스: 멀리 뛰기

문제

코딩테스트 연습 - 멀리 뛰기

 

문제 풀이

 멀리 뛰기를 할 수 있는 방법이 1칸 또는 2칸으로 정해져 있다. 이때 N개의 칸을 뛰고자 하는 경우, 경우의 수가 몇 개인지 찾는 문제이다. 이는 각 경우에 따라 어떤 규칙을 이루는지 확인하면 쉽게 해결할 수 있다.

 

• N이 1인 경우
  • 1개 : 1칸
• N이 2인 경우
  • 2개 : (1 + 1칸), 2칸
• N이 3인 경우
  • 3개 : (1 + 1 + 1칸), (2 + 1칸), (1 + 2칸)

 즉 N에 따라 `dp[N] = dp[N - 1] + dp[N - 2]`라는 점화식을 이끌어 낼 수 있다. 해당 점화식을 통해 구해진 답이 문제에서 찾고자 하는 답이다.

 

코드

def solution(n):
    # 0, 1을 1로 초기화하여 점화식에 사용.
    dp = [1, 1] + [0] * n
    
    for i in range(2, n):
        dp[i] = dp[i - 1] + dp[i - 2]
        
    return dp[-1] % 1234567