Programmers - 멀리 뛰기

---

title: Programmers - 멀리 뛰기
date: 2022-07-14
tags:

• Algorithm
• DP

---

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

문제 요약

1칸, 혹은 2칸씩 뛸 수 있을 때, n번째 칸에 도달하는 방법 % 1234567을 return한다.

문제 풀이

전형적인 DP 문제이다. 이전에 풀었던 2 x n 타일링과 매우 유사한 문제이다.
한 번에 1칸이나 2칸을 뛸 수 있다. 그렇다면 n >= 3 일 경우, n-2에서 2칸 + n-1에서 1칸이 n번째에 도달하는 경우의 수이다.
이것을 프로그램으로 작성한 것이 끝이다.

프로그램

int solution ( int n )
{
    int irgDP [ 3 ] = { 0 , 1 , 1 } ;



    for ( int i = 1 ; i < n ; ++i )
    {
        irgDP [ 0 ] = irgDP [ 1 ] ;
        irgDP [ 1 ] = irgDP [ 2 ] ;
        irgDP [ 2 ] = ( irgDP [ 0 ] + irgDP [ 1 ] ) % 1234567 ;
    }

    return irgDP [ 2 ] ;
}