프로그래머스[Java] - 멀리 뛰기(DP)

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

코딩테스트 연습 - 멀리 뛰기 | 프로그래머스

코드

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

풀이

Level3에 존재하는 문제지만, 간단한 DP문제다.

알고리즘 분류를 보진 않았지만 문제를 보니 DP로 접근해야 할 것 같아서 규칙을 보았다.

 

칸이 총 4개있을 때, 방법은 5가지다

1 + 1 + 1 + 1

1 + 2 + 1

2 + 1 + 1

1 + 1 + 2

2 + 2

 

칸이 총 3개있을 때, 방법은 3가지다.

1 + 1 + 1

1 + 2

2 + 1

 

칸이 총 2개있을 때, 방법은 2가지다.

1 + 1

2

 

n = 4일때를 다시 보자.

마지막에 1칸을 뛸 경우(빨간색 숫자) 그 앞칸(n = 3)의 방법에서 +1만 하면 된다. 따라서 dp[i-1]

마지막에 2칸을 뛸 경우(보라색 숫자) 그 앞앞칸(n = 2)의 방법에서 +2만 하면 된다. 따라서 dp[i-2]

 

x + ... + x + 1

x + ... + x + 2

 

마지막에 1칸을 뛰어 도착하는 경우, 그 앞칸을 밟고 1칸을 뛴 경우이므로, dp[i-1] 이다.

마지막에 2칸을 뛰어 도착하는 경우, 그 앞앞칸을 밟고 2칸을 뛴 경우이므로, dp[i-2]이다.

따라서 점화식은 다음과 같다.

dp[i] = dp[i-2] + dp[i-1]

 

n의 범위가 2000까지이므로, n이 일정 수 이상에선 int범위를 벗어나므로,

dp[i]값을 저장할때 1234567을 나눈 나머지로 저장한다.(문제에서 주어짐)