[JAVA] 멀리 뛰기

< 풀이 >

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

 

✏️ 풀이 방법

 

효진이는 한번에 1칸, 또는 2칸을 이동할 수 있다. 

ex)  n=1 일 때, 1칸 이동하는 방법: 1가지

       n=2 일 때, 2칸 이동하는 방법 ( 1칸씩 2번 이동, 2칸씩 한 번 이동) : 2가지

       n=3 일 때, 3칸 이동하는 방법 ( 1칸씩 3번 이동, 1칸 2칸 이동, 2칸 1칸 이동) : 3가지 

=> 이것을 점화식으로 만들면 arr [ i ] = arr [ i - 1 ] + arr [ i -2 ]  (  [ i-1] 칸 까지 오는 경우의 수와 [i -2] 칸까지 오는 경우의 수를 더함 ) 

 

✍🏻 느낀점

 

 이렇게 푸는 방식을 dp 알고리즘이라고 한다는데, 처음에 이 문제를 봤을 때는 어떻게 풀어야 할 지 감이 안잡혔던 것 같다. 다른 사람들의 풀이를 보고 이해를 했다. '경우의 수' 를 구한 것이라고 생각하고 보면 어렵지 않은데, 그냥 식 자체만 보면 이해가 잘 안가는 부분이 있는 것 같다. 이번에 이런 유형의 문제가 있다는 것도 배웠으니 다음에는 당황하지 말자ㅎㅎ,,

 

 

 

 

 

 

 

 

 

 

 

 

 

참고 블로그

---

https://hstory0208.tistory.com/entry/Java%EC%9E%90%EB%B0%94-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv2-%EB%A9%80%EB%A6%AC-%EB%9B%B0%EA%B8%B0DP%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98