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

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

1과 2로만 갈 수 있다는 조건에서 규칙이 발생할 거라고 유추해 규칙을 찾기 위해 4까지 몇가지의 경우의 수가 나오는지 보다가 DP문제임을 확신

 

F(1) = 1

F(2) = 2

F(3) = 3 // F(1) + F(2)

F(4) = 5 //  F(2) + F(3)

F(n) = F(n-1) + F(n-2)

 

DP : Bottom-Up (Tabulation 방식) 을 사용함

https://godgjwnsgur7.tistory.com/109

[Algorithm C#] 동적 계획법(DP) / Memoization, Tabulation

 

주석 참조

    public class Solution
    {
        public long solution(int n)
        {
            int answer = 0;

            // F(1) = 1, F(2) = 2, F(3) = 3
            if (n <= 3)
                return n;

            int dp1 = 2; // F(2)
            int dp2 = 3; // F(3)

            // F(4)부터 구함
            for (int i = 4; i <= n; i++)
            {
                // 1234567보다 커지면 나머지를 저장
                answer = (dp1 + dp2) % 1234567;

                // 다음 연산을 위한 세팅
                dp1 = dp2;
                dp2 = answer;
            }

            return answer;
        }
    }