프로그래머스 | Level 2 | 멀리 뛰기

Programmers | Level 2 | 멀리 뛰기

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Dynamic Programming

Description

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

Constraints

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

Examples

n	result
4	5
3	3

Solutions

• ⏳ TC: O(n)
• 💾 SC: O(n)

import java.util.*;

class Solution {
    public long solution(int n) {
        // dp 배열 선언 및 초기값을 설정
        long[] dp = new long[n + 1];
        
        // 초기 조건 설정
        dp[1] = 1;
        if (n >= 2) {
            dp[2] = 2;
        }
        
        // DP 테이블 채우기
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
        }
        
        // 결과 반환
        return dp[n];
    }
}

Approaches

이 문제는 동적 계획법(Dynamic Programming, DP)을 사용하여 해결할 수 있습니다. 효진이는 한 번에 1칸 또는 2칸을 뛸 수 있기 때문에, 각 위치에 도달하는 방법의 수는 이전 위치들의 방법 수를 이용해 계산할 수 있습니다. 이를 좀 더 자세히 설명하겠습니다.

효진이가 n번째 칸에 도달하는 방법의 수를 dp[n]이라고 할 때, n번째 칸에 도달하기 위해서는 (n-1)번째 칸에서 1칸을 뛰거나, (n-2)번째 칸에서 2칸을 뛰어야 합니다. 따라서 dp[n]은 dp[n-1]과 dp[n-2]의 합이 됩니다. 즉, 다음과 같은 관계식을 세울 수 있습니다:

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

이를 통해 각 칸에 도달하는 방법의 수를 재귀적으로 계산할 수 있습니다. 하지만, 재귀적으로 접근하면 중복 계산이 많아지므로 비효율적입니다. 따라서 동적 계획법을 사용해 중복 계산을 피하고 효율적으로 문제를 해결할 수 있습니다.

문제를 해결하는 과정은 다음과 같습니다:

• 초기 조건 설정:
  • dp[1]은 1칸을 뛰는 방법 1가지입니다. 따라서 dp[1] = 1입니다.
  • dp[2]는 1칸을 두 번 뛰는 방법과 2칸을 한 번에 뛰는 방법, 총 2가지입니다. 따라서 dp[2] = 2입니다.
• DP 테이블 채우기:
  • 초기 조건을 설정한 후, 3번째 칸부터 n번째 칸까지 dp 배열을 채워나갑니다. 각 칸에 도달하는 방법의 수는 앞서 설명한 관계식을 사용하여 계산합니다. 이를 일반화하면 다음과 같습니다:
  • 왜 1234567로 나누는가? 문제에서 요구하는 대로 결과가 매우 큰 수가 될 수 있으므로, 매 단계마다 1234567로 나눈 나머지를 저장하여 overflow를 방지합니다.
• 최종 결과 반환: dp 배열을 채운 후, dp[n] 값을 반환하면 됩니다.

이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도는 O(n)입니다. 이는 주어진 문제를 효율적으로 해결하는 데 충분합니다.