프로그래머스 [C#] 멀리뛰기

문제

 

풀이

public class Solution {
    public long solution(int n) {
        long answer = 0;
        int MOD = 1234567;
        int[] count = new int[n + 1];
        count[0] = 1;
        count[1] = 1;

        for (int i = 2; i <= n; i++)
        {
            count[i] = (count[i - 1] + count[i - 2]) % MOD;
        }
        
        answer = count[n];
        
        return answer;
    }
}

이번 문제의 핵심은 정답이 피보나지 수열의 형태를 띄고 있다는 것을 알아채는 것이 핵심입니다.

피보나치 수열이란 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 의미합니다.

ex) 1,1,2,3,5,8,13,21

 

효진이는 1,2 칸씩 뛸 수 있습니다. 효진이가 멀리뛰기에 사용할 칸의 수 n일 때,

피보나치 수열의 점화식 F(n) = F(n-1) + F(n-2)를 적용했을 때 나온 수열의 값이 곧 효진이가 끝에 도달할 방법의 가지 수 입니다.

이는 아래와 같이 나타낼 수 있습니다.

F(1) = 1
F(2) = 2
F(3) = 3
F(4) = 5
F(5) = 8

 

식을 조금 더 풀어서 나타내면,

 

점화식 : F(n) = F(n - 1)  + F(n - 2)

n이 2일 경우,
F(2) = F(2 - 1) + F(2 - 2)
F(2) = F(1) + F(0)
F(2) = 1 + 1 = 2

n이 3일 경우,
F(3) = F(3 - 1) + F(3 - 2)
F(3) = F(2) + F(1)
F(3) = 2 + 1 = 3

n이 4일 경우,
F(4) = F(4 - 1) + F(4 - 2)
F(4) = F(3) + F(2)
F(4) = 3 + 2 = 5

 

 

즉 위와 같이, 경우의 수 n은 이전 두 항의 경우의 수를 합한 값이 되는 형태를 지니고 있습니다.

조금 더 풀어서, 왜 경우의 수가 F(2) = 2, F(3) = 3이 나오는지, 문제를 예시를 적용하여 설명하겠습니다.

 

효진이는 1칸 또는 2칸을 뛸 수 있다.

점화식 : F(n) = F(n - 1)  + F(n - 2)

n이 2일 경우, 
경우의 수는 (1,1), (2)이다. 총 2가지

n이 3일 경우, 
경우의 수는 (1,1,1), (1,2), (2,1)이다. 총 3가지

n이 4일 경우,
경우의 수는 (1,1,1,1), (1,2,1), (1,1,2), (2,1,1), (2,2)이다. 총 5가지

n이 5일 경우,
경우의 수는 (1,1,1,1,1), (1,1,1,2), (1,1,2,1), (1,2,1,1), (2,1,1,1), (1,2,2), (2,1,2), (2,2,1)이다. 8가지

 

이와 같이 효진이가 뛸 수 있는 방법의 가지 수가, 피보나치 수열과 같은 형태를 띄고 있습니다.

 

이 문제는 효진이가 뛸 수 있는 방법인 (1,1,1), (1,2), (2,1)이라는 숫자에 집중하기보다,

효진이가 n번 째 칸에 도달 할 수 있는 방법의 가지 수 3에 집중해야합니다. (n이 3일 경우)

그 이유는 효진이가 마지막 칸에 도달하는 모든 경우가 그 이전 칸까지의 경우의 수로부터 결정되기 때문입니다.