[Programmers_Python] 멀리 뛰기

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

프로그래머스

내 풀이 방식

처음에 DP방식으로 풀지 않고 itertools를 이용해서 구했는데 시간 초과가 발생했다,,, 처음에 생각해낸 방식이고 당연히 시간 초과가 날 것이라 생각했지만 역시나 시간 초과가 나서 다른 방식을 생각해내야했지만, 아직 DP에 익숙하지 않아서 그런지 DP로 풀어야겠다는 생각을 하지 못했다.

import itertools

def solution(n):
    n_cnt = n // 2
    answer = 0
    for i in range(n_cnt + 1):
        sub_lst = [2] * i
        sub_lst.extend([1]*(n - i*2))
        iter_lst = list(set(itertools.permutations(sub_lst,len(sub_lst))))
        answer += len(iter_lst)
    return answer

올바른 풀이

다른 분들은 어떻게 풀었는지 참고해보니 다들 DP방식으로 푼 것으로 보였다,,,

• n = 1일 때, 한 가지 경우 밖에 없다 $\rightarrow \ dp[1] = 1$
• n = 2일 때, [(1,1), (2)]로 두 가지 경우 $\rightarrow \ dp[2] = 2$
• n = 3일 때, [(1,1,1), (2,1), (1,2)]로 세 가지 경우 $\rightarrow \ dp[3] = 3$
• n = 4일 떄, [(1,1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2)]로 다섯 가지 경우 $\rightarrow \ dp[4] = 5$
• 이렇게 확인해 보면 $dp[i] = dp[i-1] + dp[i-2]$라는 점화식을 찾을 수 있다.

def solution(n):
    if n == 1:
        return 1
    else:
        dp = [0,1,2]
        for i in range(3, n + 1):
            dp.append(dp[i-1] + dp[i-2])
        # print(dp)
    return dp[-1] % 1234567

이 문제를 풀면서 어렵지 않은 문제지만 아직 동적 프로그래밍을 쓰는데 많이 미숙하다는 것을 깨달았다. 어떤 경우에 동적 프로그래밍을 이용해야하는지?? 같은 것들을 숙지해야겠다!