멀리 뛰기 (C#)

📌문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

📌제한 사항

n은 1 이상, 2000 이하인 정수입니다.

📌입출력 예

n result
4 5
3 3

📌입출력 예 설명

입출력 예 #1
위에서 설명한 내용과 같습니다.
입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

🔍피보나치 수열

이번 문제를 풀기위해 사용되는 정의이다.

먼저 점화식을 만들면

• 1칸일 때 F(0) = 1 [1]
• 2칸일 때 F(1) = 2 [1, 1], [2]
• F(n) = F(n-1) + F(n-2)
  위 식을 사용해 (n - 1)칸일 때의 방법을 피보나치 수열로 구할 수 있다.

💡풀이

위 식을 적용하기 n개 만큼 배열을 만들어 둔다.
long[] cases = new long[n];

n이 1일 때 바로 1을 return 한다.

if (n == 1)
    return 1;

1칸 F(0)과 2칸 F(1)의 개수를 만든다.

cases[0] = 1;
cases[1] = 2;   

구한 방법에 1234567을 나눈 나머지를 F(i)으로 할당하고 n까지 for문을 돌며 피보나치 수열을 적용한다.

for(int i = 2; i < n; i++)
    cases[i] = (cases[i - 2] + cases[i - 1]) % 1234567;    

n칸의 방법이 F(n - 1)이므로 cases[n-1] 을 반환한다.
return cases[n - 1];

전체코드

public long 멀리뛰기(int n)
{
    long[] cases = new long[n];

    if (n == 1)
        return 1;

    cases[0] = 1;
    cases[1] = 2;            

    for(int i = 2; i < n; i++)
        cases[i] = (cases[i - 2] + cases[i - 1]) % 1234567;

    return cases[n - 1];
}

피보나치 수열을 써야 하는지 몰랐다.
여러 케이스들을 확인하고 어떤 방식을 적용하는지 빠르게 이해 하는게 중요한 듯 하다.
그리고 해당 방식의 공식(?)을 알아두는 것도 좋아 보인다.