[프로그래머스] 멀리 뛰기 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한 번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567을 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return 하면 됩니다.

2. 입력

• n은 1 이상, 2000 이하인 정수입니다.

3. 예제

n	result
4	5
3	3

4. 풀이

가장 짧게 점프한 거리인 n이 1인 경우 점프할 수 있는 경우의 수는 [1] 1가지 경우이다.

 

다음 짧은 거리 n이 2인 경우는 점프할 수 있는 경우의 수는 [11, 2] 2가지 경우이다.

 

다음 짧은 거리 n이 3인 경우는 점프할 수 있는 경우의 수는 [111, 12, 21] 3가지 경우이다.

 

문제에서 점프할 수 있는 거리는 1과 2 두 가지라고 하였다.

 

그럼 항상 점프한 거리는 점프하고자 하는 위치에서 1칸 전인 위치와 2칸 전인 위치에서 점프하여 오는 경우로 나누어서 볼수 있다.

• 1칸 전인 구간
  3에서 1칸 전인 구간은 2이며 2는 [11, 2] 2가지 경우로 점프할 수 있다. 그러므로 3은 2까지 점프한 뒤 1만큼 점프를 하면 3으로 올 수 있게 된다.
• 2칸 전인 구간
  3에서 2칸 전인 구간은 1이며 1은 [1] 1가지 경우로 점프할 수 있다. 그러므로 3은 1까지 점프한 뒤 2만큼 점프를 하면 3으로 올 수 있게 된다.
  
  

위 두 가지 경우를 이용하여 점화식을 만들면 DP[i] = DP[i-1] + DP[i-2]가된다.

 

3의 경우의 수를 알려면 2까지 점프 경우의 수 + 1까지 점프 경우의 수가 된다.

 

6의 경우의 수를 알려면 5까지 점프 경우의 수 + 4까지 점프 경우의 수가 된다.

 

위 점화식을 이용하여 배열을 생성하여 문제를 풀 수 있다.

 

5. 코드

전체 코드는 Git에 있습니다.

long[] dp = new long[n + 1];
dp[0] = 1;
dp[1] = 1;

for (int i = 2; i <= n; i++)
	dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;

return dp[n];