<dp> 프로그래머스 멀리 뛰기

문제

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

프로그래머스

 

풀이

class Solution {
    public long solution(int n) {
        long answer = 0;
        
        int[] D = new int[2001];
        D[1]=1;
        D[2]=2;
        for(int i=3; i<=2000; i++){
            D[i]=(D[i-1]+D[i-2])%1234567;
        }
        
        return D[n];
    }
}

 

n이 일정 수 이상에선 int 범위를 벗어나 d[i]값을 저장할 때 123456을 나눈 나머지로 저장해야한다.

 

칸이 4개 D[i] =D[i-1]+D[i-2] 빨간색+ 파란색 수를 더한 수 

1+1+1+1

1+2+1

2+1+1

1+1+2

2+2

 

 

칸이 3개 D[i-1]

1+1+1

1+2

2+1

 

칸이2개 D[i-2]

1+1

2