Long jump

해당 문제는 여기에서 확인하실 수 있습니다.

문제를 해결하기 위해 효진이가 한 번에 1칸 또는 2칸을 뛸 수 있다는 규칙을 바탕으로 동적 계획법을 활용할 수 있습니다. 각 칸에 도달하는 방법의 수는 이전 칸들의 방법을 이용해 계산할 수 있는데, 이를 수식으로 표현하면 n 칸에 도달하는 방법은 n-1 칸에서 1칸을 더 뛰거나, n-2 칸에서 2칸을 더 뛰는 경우로 나뉩니다. 따라서 n 칸에 도달하는 방법의 수는 n-1 칸까지 도달하는 방법과 n-2 칸까지 도달하는 방법을 더한 값이 됩니다. 이 규칙은 피보나치 수열과 동일한 형태를 가지고 있어, 이를 기반으로 동적 계획법을 적용할 수 있습니다.

동적 계획법을 적용하기 위해, 각 칸에 도달하는 방법의 수를 저장하는 배열을 사용하여 처음부터 차례대로 계산해 나갑니다. 이렇게 하면 중복된 계산을 방지할 수 있으며, 효율적으로 답을 구할 수 있습니다.

또한 문제에서는 결과 값이 매우 커질 수 있기 때문에, 계산 중간마다 1234567로 나눈 나머지를 저장하여 최종 결과를 구해야 합니다.

class Solution {
  public long solution(int n) {
    // n이 1일 경우 방법은 1가지
    if (n == 1) return 1;
    
    // n이 2일 경우 방법은 2가지
    if (n == 2) return 2;

    // 각 칸에 도달하는 방법의 수를 저장하는 배열
    long[] dp = new long[n + 1];
    
    // dp[1]은 1칸을 이동하는 방법의 수
    dp[1] = 1;
    
    // dp[2]는 2칸을 이동하는 방법의 수
    dp[2] = 2;

    // 3칸 이상부터는 피보나치 수열처럼 계산
    for (int i = 3; i <= n; i++) {
      // dp[i]는 dp[i-1]과 dp[i-2]의 합을 1234567로 나눈 나머지
      dp[i] = (dp[i-1] + dp[i-2]) % 1234567;
    }

    // n번째 칸에 도달하는 방법의 수 반환
    return dp[n];
  }
}