[C++로 풀이] 멀리 뛰기 (dp)⭐⭐⭐

📌 멀리 뛰기

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이 ⭕

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {
    long long arr[2001];
    arr[0] = 1;
    arr[1] = 1;
    for(int i = 2; i <= n; i++)
        arr[i] = (arr[i - 1] + arr[i - 2]) % 1234567;
    
    return arr[n];
}

“피보나치 수열”을 Dynamic Programming 방식으로 풀었다.

프로그래머스 2 X n 타일링 문제와 똑같다! 피보나치 수열 구하는 문제다. 타일링 문제에서 가로 1, 2 사각형으로 만들 수 있는 모든 타일링 방법과 효진이가 1칸 혹은 2칸 둘 중 하나로 멀리 뛸 수 있는 모든 방법이 대응된다.

✈ 피보나치인 이유

1과 2로 만드는 조합.

• 효진이가 멀리 뛰는 n가지 방법 arr[n]
  • n-1가지 방법에서 각 방법에 1 칸씩만 더 가게 하면 됨 arr[n-1]과 동일
  • n-2가지 방법에서 각 방법에 2 칸씩만 더 가게 하면 됨 arr[n-2]과 동일

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기