[프로그래머스] 멀리 뛰기(JAVA)

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

프로그래머스

 

 

🖊️ 문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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하면 됩니다.

🖊️제한 사항

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

🖊️ 입출력 예

n	result
4	5
3	3

 

🖊️ 입출력 예 설명

입출력 예 #1
위에서 설명한 내용과 같습니다.

입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

 

🖊️ 문제 풀이

입출력 예시를 보고 우선 n=1, n=2, n=3, n=4, n=5인 경우에 경우의 수를 계산해보았다.

n = 1일 때는 무조건 한 칸만 이동하면 되니까 dp[1] = 1이 된다.

n = 2일 때는 (1,1) 또는 (2)로 이동하면 되니까 dp[2] = 2가 된다.

n = 3, n= 4일 때는 입출력 예시를 보면 되니까 건너뛰고... n = 5일 때는(1,1,1,1,1), (2,1,1,1), (1,2,1,1), (1,1,2,1), (1,1,1,2), (2,2,1), (2,1,2), (1,2,2)로 dp[5] = 8이다.

 

이렇게 경우의 수를 확인해보면서 규칙을 찾아볼 수 있었는데, n=3일 때는 dp[3] = dp[2] + dp[1] = 3, n=4일 때는 dp[4] = dp[3] + dp[2] = 5,  n=5일 때는 dp[5] = dp[4] + dp[3] = 8로 계산된다.

이걸 정리해보면, dp[n]  = dp[n-1]+dp[n-2]의 식으로 정리할 수 있다.

도출해낸 식을 이용해서 문제를 풀어보았다.

 

🖊️코드

package 프로그래머스Lv2;

import java.util.Arrays;

public class 멀리_뛰기 {
  public static long solution(int n) {
    long dp [] = new long[n+1];
    if(n==1){
      return 1;
    }else if(n==2){
      return 2;
    }

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

  }

  public static void main(String[] args) {
    System.out.println(solution(4));
  }

}

경우의 수를 저장해줄 때 123467로 나눈 나머지를 저장해주는 것 잊지 말기!