프로그래머스 멀리 뛰기 (C#)

프로그래머스

효진이는 한번에 1칸, 2칸을 이동할 수 있을 때, N으로 이동하는 경우의 수를 구해주세요.

 

 

풀이 방법

점화식을 구해줘야 합니다.

 

1칸을 이동할 때는 경우의 수가 1개

2칸을 이동할 때는 경우의 수가 2개

3칸을 이동할 때는 경우의 수가 3개

4칸을 이동할 때는 경우의 수가 5개

즉 i칸을 이동할 때는 dp[i-1] + dp[i-2]칸이 됩니다. 즉,

count[i] = (count[i-1] + count[i-2]) % MOD;

위의 코드가 점화식이 되겠습니다.

 

해당 점화식을 이용하여 i가 N이 될 때 까지 반복문을 돌면 됩니다.

 

 

정답 코드

public class Solution {
    public long solution(int n) {
        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;
        
        return count[n];
    }
}