프로그래머스 / DP / 멀리 뛰기

문제

---

 

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

프로그래머스

 

입출력

---

 

해설

---

 

N에 도달하는 여러 가지 방법을 1234567으로 나눈 나머지로 리턴하여라.

 

문제를 잘 읽어보면 한 칸에서 두 칸만 뛸 수 있다는 것이 이 문제의 KeyPoint이다.

 

결국 내가 1번 칸이었으면 다음으로는 2번칸, 3번칸으로만 갈 수 있다는 것이고 7번칸이면 8번칸, 9번칸으로 갈 수 있다는 것이다.

다시 말해 N칸에 도달하기 위해서는 N-1칸, N-2칸에서 올 수 있으므로 N-1칸과 N-2칸에서 오는 경우의 수를 더해주는 것이다.

 

그러면 DP테이블은 현재 i칸에 도달하는 경우의 수라고 정의내릴 수 있을 것이다.

그래서 다음과 같은 점화식이 만들어진다.

DP[i] = DP[i-1] + DP[i-2]

 

그런데 문제가 있다. 결과만 %1234567하기에는 계산하던 도중에 오버플로우가 날 경우가 있다. (파이썬은 물론 없지만..)

그렇기에 다음과 같은 점화식이 탄생하게 된다.

DP[i] = (DP[i-1] + DP[i-2]) % 1234567

 

이거는 모듈러 연산에 의해서 다음과 같은 사항이 참이기에 가능한 점화식이다.

(A + B) % 1234567 == ((A % 1234567) + (B % 1234567)) % 1234567

 

정답코드

---

'''
'25. 08. 15

1. N에 도달할 수 있는 방식이 여러가지가 있다.
2. 해당 가짓수를 모두 세어라
    2-1. 한 칸 혹은 두 칸만 뛸 수 있음
3. 수가 커질 수 있으므로 1234567로 나눈 나머지를 리턴하여라

1칸 1
2칸 1 1
    2
3칸 1 1 1
    2 1
    1 2
4칸 1 1 1 1
    2 1 1
    1 2 1
    1 1 2
    2 2
Dp[i] = (Dp[i - 1] + Dp[i - 2]) % MOD가 되겠다.
'''
MOD = 1234567
def solution(n):
    dp = [0] * 2001
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
    return dp[n]

 

깃허브 : https://buly.kr/EooRE4T

유튜브 : https://youtu.be/zDmIfd6LLNA