[코딩테스트 연습] 멀리 뛰기

 

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

---

DP 문제입니다.

푸는 방식은 다양하겠지만 값을 저장함으로써 중복되는 연산은 O(1)에 리턴하는 로직이 중요합니다.

 

효진이는 한 번에 1칸 또는 2칸을 뛸 수 있으므로,

 

N번째 칸까지 점프하는 방법을 구한다면

 

1. N-1번째 칸에서 + 1 점프하는 방법

2. N-2번째 칸에서 + 2 점프하는 방법

 

JUMP[N] = JUMP[N-1] + JUMP[N-2] 의 점화식이 성립하게 됩니다.

 

문제 조건처럼 1234567로 나눌 때 모듈러 연산자 법칙을 적용하면 답을 얻을 수 있습니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG12914.cc