프로그래머스 12914 멀리 뛰기 파이썬 풀이

난이도 Lv. 4

풀이일 : 2410244

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

프로그래머스

---

문제

---

아이디어

칸	0	1	2	3	4	5
방법 수	0	1	2	3	5	8

• 3부터는 (n-1) + (n-2) 형태로 방법의 수가 증가한다
• dp로 방법의 수를 더해나가자
• 1234567로 나눈 나머지를 기록하여 숫자가 커지지 않게 조절하자

---

풀이

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

• dp 크기는 n이 1일때의 런타임에러 방지를 위해 n+1로 설정
• 반복문을 순회하며, i가 0, 1일 경우 예외 처리로 dp 기록
• i가 2 이상일 경우, (n-1) + (n-2) 정보를 더해 dp 기록
• 빠른 계산을 위해, 숫자가 커지는 것을 방지하기 위해 처음부터 1234567로 나누어 기록