99클럽 코테 스터디 22일차 TIL (멀리 뛰기 - 프로그래머스)

오늘의 학습 키워드:  DP

문제: 멀리 뛰기

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

풀이

이번에도 DP문제가 나왔습니다.

칸에 도달하는 방법은 두 가지 방법이 있습니다.

1. 한 칸 뛰기

2. 두칸 뛰기

 

따라서 따져보아야할 가짓수는 한 칸 전의 값, 두 칸 전의 값입니다..

도달 가능한 수의 합은 앞의 두칸의 합과 동일하게 됩니다. (피보나치..?)

코드로 구현해보면 아래와 같습니다.

def solution(n):
    jump = [0 for _ in range(n)]
    
    for i in range(n):
        if i == 0:
            jump[i] = 1
        elif i == 1:
            jump[i] = 2
        else:
            jump[i] = jump[i-1]+jump[i-2]
    
    return jump[-1]%1234567