LV2 멀리 뛰기 (Java)

 

---

 

문제

 

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

프로그래머스

풀이

dp로 풀이했다.

 

1칸 또는 2칸만 움직일 수 있다는걸 반대로 생각하면 -> 내가 있는 현재 위치 - 1 에서 오는 방법, 내가 있는 현재 위치 -2 에서 오는 방법 두가지가 있다.

 

따라서 점화식은 d[i] = d[i-1] + d[i-2] 로 정의할 수 있다.

 

그리고 값 오버 플로우를 대비해서 dp 배열에 저장할때부터 % 연산하는걸 주의해야 한다. 마지막에 return할때 처리할려면 이미 배열안은 오버 플로우가 나있는 상황이니 말이다.

 

코드

import java.util.*;

class Solution {
    
    public long solution(int n) {
        long d[] = new long[2001]; // n번째 칸에 도달하는 방법의 개수
        d[1] = 1;
        d[2] = 2;
        
        for(int i=3; i<2001; i++){
            d[i] = (d[i-1] + d[i-2])%1234567;
        }
        
        return d[n];
    }
}

 

후기

 

백준에 계단 문제가 생각난다. 이런 dp만 있다면..