[프로그래머스] 멀리 뛰기 - python

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

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

나는 문제 보자마자... 백트레킹이다 하고 접근했는데.... 이게 다이나믹 이었다... 하하

오랜만에 푸는 문제라 감각이 많이 떨어졌다. 하하

 

다시 하루 생각해봤는데 전형적인 메모제이션이다!

dp의 유형은 문제를 잘게 조깨는게 중요하다.

아래의 문제를 잘 해석해보자 중요한 부분은 

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

이 부분이다.

 memo[1] = 1
 memo[2] = 2
    for i in range(3,n+1):
        memo[i] = memo[i-1] + memo[i-2]

우리는 점프를 1칸 2칸 할수 있다. 왜 두개를 더하면 다음꺼의 가지수에 포함되는지를 알아보자.

그 이유는

1칸 전의 경우의 수는 이제 마지막 1칸만 뛰면 도착이므로 그 전까지의 경우를 고려한 것이도

2칸 전의 경우의 수는 이제 마지막 2칸만 뛰면 도착지에 도착하는 경우의 수를 고려한 것이다.

이렇게 하면 쉽게 이해가 가능하다

 

예를 들어보면

memo[1] = 1 1칸 뛰는 경우 1개 ,  memo[2] = 2 는 1칸 2번 뛰는 경우, 2칸 한번에 뛰는 경우라 2가지이며,

 

memo[3] = memo[1] + memo[2]  인 이유는 memo[1] 까지 뛰는 경우에 이제 1칸 남은 거에 memo[2]까지의 경우에 2칸 만 뛰면 되는 경우를 더해서 나온 것이다.

이걸로 해설 끝!