프로그래머스 - 멀리 뛰기

문제 설명

제한 사항 및 입출력

풀이

전형적인 DP 문제이다. 첫 번째 칸부터 선형적으로 순회하며 칸에 도달할 때마다 이전 칸에 도달하는 방법들을 모두 더해주면 된다.

 

dp테이블의 정의는 다음과 같다.

dp[i] = i칸에 도달할 수 있는 경우의 수

내 코드

def solution(n):
    dp = [0] * n
    
    # n이 1일땐 1반환
    if n == 1:
        return 1
    dp[0] = 1
    dp[1] = 1
    
    for i in range(n-1):
        dp[i+1] += dp[i]
        try:
            dp[i+2] += dp[i]
        except:
            continue
    
    return dp[-1] % 1234567

인덱스가 넘어가는 경우는 try - except로 처리해주었다.

고찰

너무 정석적인 dp문제라 다른 풀이는 딱히 떠오르지 않는다...