프로그래머스 LV2 멀리뛰기(DP)

첫번째 칸에는 1로만 뛸 수 있는 경우 - 1

두번째 칸에는 2로만 뛸 수 있는 경우와 1로만 뛸 수 있는 경우 - 2

세번째 부터는 1, 2 이용해서 뛸 수 있는 경우 - 3

 

점화식 세워서 푸는 문제였다.

 

 

def solution(n):
    if n<3:
        return n
    d=[0]*(n+1)
    d[1]=1
    d[2]=2
    for i in range(3,n+1):
        d[i]=d[i-1]+d[i-2]
    return d[n]%1234567

 

 

- dfs 풀이는 시간 초과 발생..

cnt = 0


def dfs(number, n):
    global cnt
    
    
    if number < n:
        number = number%1234567
        dfs(number + 1, n)
        dfs(number + 2, n)
    
    if number == n:
        cnt += 1
        return
        

def solution(n):
    dfs(0, n)
    answer = cnt % 1234567
    return answer