[코딩테스트] 프로그래머스 멀리 뛰기 파이썬(Python)

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

프로그래머스

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

이 문제는 숨겨진 점화식을 찾아내 DP로 해결했습니다.

 

n = 1 : (1칸), result = 1

n = 2 : (1칸, 1칸), (2칸) result = 2

n = 3 : (1칸, 1칸, 1칸), (1칸, 2칸), (2칸, 1칸) result = 3

n = 4 : (1칸, 1칸, 1칸, 1칸), (1칸, 1칸, 2칸), (1칸, 2칸, 1칸), (2칸, 1칸, 1칸), (2칸, 2칸) result = 5

n = 5 : (1,1,1,1,1), (1,1,1,2), (1,1,2,1),(1,2,1,1),(2,1,1,1),(1,2,2),(2,1,2),(2,2,1) result = 8

 

위의 과정을 아래와 같은 점화식으로 표현할 수 있습니다.

A[1] = 1

A[2] = 2

A[3] = 3

A[4] = 5

A[5] = 8

...

A[n] = A[n-1] + A[n-2]

 

문제를 해결하는데 필요한 식을 구했고 이 식을 코드로 작성을 할 때 재귀로 해결할 수 있지만

재귀로 풀 경우에는 시간초과가 나기 때문에 DP로 해결하였습니다.

 

array = [0]* (n+1)

n을 구해야 하기 때문에 n+1로 모든 값은 0으로 초기화를 해줍니다.

for i in range(n+1):
        if i <= 1:
            array[i] = 1
        else:
            array[i] = array[i-2] + array[i-1]

n+1 까지 i를 증가시키며 반복문을 진행하는데 이때 i가 1보다 작을 때 즉 0과 1일 때에는 array[i]를 1로 초기화 해줍니다.

array[0]과 array[1]을 1로 초기화해줘야 array[2]를 올바르게 구하고 나머지 array[i]를 구할 수 있습니다.

 

for문을 다 진행하고 난뒤

문제에서 주어진 대로 우리는 결과에 % 1234567한 값을 반환해야하기 때문에

return array[n] % 1234567

위의 코드로 문제를 해결합니다.