[Java/Algorithm] DP - 제한된 이동 거리로 목적지까지 가는 경우의 수

목적지까지 가는 방법의 수를 구하는 문제를 풀며 내용을 정리했습니다. 개인적으로 풀이가 어렵게 느껴진 문제라 꼭 정리해야겠다고 생각했습니다. DP 알고리즘을 쓰려면 꼼꼼하게 세부적인 사항을 고려해서 변수를 이용하고 값을 초기화해야 한다는 걸 배울 수 있었습니다 👍

문제 설명

최대 이동 거리 k와 목적지 n이 주어졌을 때, 위치 0에서 목적지 n까지 가는 방법의 수를 구한다. 단, 연속해서 동일한 거리를 이동할 수 없다.

입출력 예시

• 목적지 n: 4
• 최대 이동 거리 k: 2

조건

• 위치 0에서 출발해서 위치 4까지 가려고 합니다.
• 최대 이동할 수 있는 거리는 1 또는 2입니다.
• 동일한 거리로 연속해서 이동할 수 없습니다.

풀이 과정

이 문제를 해결하려면 목적지에 도착하기 위한 여러 이동 거리의 조합을 모두 계산해야 합니다. 하지만 모든 과정을 처음부터 계산하는 것은 오래 걸리기 때문에 이전 단계에서 구한 계산 값을 재사용하는 방식으로 푸는 것이 바람직합니다. 한 번 이동할 때 선택한 거리에 따라서 각각의 경우의 수를 구하고, 그 다음 이동 거리를 선택할 때 이전에 구한 경우의 수를 재사용해서 모든 경우의 수를 저장해 나가는 과정을 목적지에 도달할 때까지 반복하는 방법으로 풀 수 있습니다.

이전 선택으로 나오게 된 경우의 수가 다음 선택으로 나올 수 있는 경우의 수에 영향을 줍니다. 해결해야 하는 문제의 이러한 특징을 파악하고 코드를 만드는 것이 중요한 포인트인 것 같습니다. 이러한 알고리즘을 DP (다이나믹 프로그래밍)이라고 합니다.

다이나믹 프로그래밍 (동적 계획법, DP)
동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다. (namuwiki)

먼저, 경우의 수를 누적해서 저장할 2차원 DP 배열을 만듭니다.

• 배열 정의: 우선 이러한 경우의 수를 모두 저장할 수 있도록 2차원 배열을 만들고 DP배열이라고 부르겠습니다. DP 배열에서 j는 도달한 위치를 나타내고, i는 선택할 수 있는 이동 거리를 나타냅니다. j 위치에서 i는 마지막으로 선택한 이동 거리이기 때문에, dp[j][i]는 "위치 j에 도달할 수 있는 방법의 수중 i를 마지막으로 선택한 총 경우의 수"를 의미합니다.

• 기본 상태 초기화: 출발지가 0에서 시작하기 때문에 dp[0][0] = 1로 초기화합니다. 값을 1로 두는 이유는 시작점에서 아무 이동도 하지 않고 그 자리에 있는 상태가 1가지 경우로 존재한다는 의미로 해석합니다. 이후의 누적 계산에서 이 값을 사용하기 때문에 출발점에서 시작해 특정 위치로 이동하는 모든 경로를 구하기 위한 초기값이라고 볼 수 있습니다. 예를 들어 dp[1][1] 값을 구하기 위해 이전 값을 가져올 때 이 초기값을 가져와서 사용하기 때문에 1로 올바르게 최종 값이 계산됩니다.

• 이중 for문: 목적지 위치 j에 대해서, 한 번에 이동할 수 있는 거리인 i에 대한 값을 계산하도록 이중 for문을 작성합니다. i의 값은 j보다 클 수 없다는 조건을 if문으로 추가합니다. 예를 들어, j가 3일 때 i는 최대 값으로 2가 주어졌으므로 한 번에 이동할 수 있는 거리는 1과 2가 됩니다.

• 연속으로 같은 거리를 이동하지 않는 조건 추가: 여기서 새로운 변수 m은 이전 단계에서 이동한 거리를 의미합니다. 이때 m != i라는 조건을 둬서 현재 이동한 거리와 이전 거리가 같을 수 없다는 조건 하에 새 경우의 수를 계산하도록 합니다. m은 0부터 탐색을 시작하는데 [j - i]를 계산할 때 0이 나올 수 있기 때문에 꼭 필요합니다. dp[j][i] = (dp[j][i] + dp[j - i][m]) % MOD; 이 부분에서 현재 목적지에 도착하기 전 단계의 모든 경우의 수를 가져오게 됩니다.

배열 모습 예시

1. 목적지 1로 이동할 때

• 거리 1만큼 이동: dp[1][1] = dp[0][0] = 1
  • 위치 0에서 1만큼 이동해서 1 위치에 도달하는 방법은 1가지입니다.

[j][i]	0	1	2
0	1	0	0
1✅	0	1	0
2	0	0	0
3	0	0	0
4	0	0	0

2. 목적지 2로 이동할 때

• 거리 1만큼 이동: dp[2][1] = dp[1][2] = 0

  • 위치 1에서 2로 1만큼 이동할 수 없습니다 (이전에 2만큼 이동한 적이 없으므로 방법의 수는 0입니다).

• 거리 2만큼 이동: dp[2][2] = dp[0][0] = 1

  • 위치 0에서 2만큼 이동해서 2 위치에 도달하는 방법은 1가지입니다.

[j][i]	0	1	2
0	1	0	0
1	0	1	0
2✅	0	0	1
3	0	0	0
4	0	0	0

3. 목적지 3로 이동할 때

• 1만큼 이동: dp[3][1] = dp[2][2] = 1

  • 위치 2에서 1만큼 이동해서 3 위치에 도달하는 방법은 1가지입니다.

• 2만큼 이동: dp[3][2] = dp[1][1] = 1

  • 위치 1에서 2만큼 이동해서 3 위치에 도달하는 방법은 1가지입니다.

[j][i]	0	1	2
0	1	0	0
1	0	1	0
2	0	0	1
3✅	0	1	1
4	0	0	0

4. 위치 4로 이동:

• 1만큼 이동: dp[4][1] = dp[3][2] = 1

  • 위치 3에서 1만큼 이동해서 4 위치에 도달하는 방법은 1가지입니다.

• 2만큼 이동: dp[4][2] = dp[2][1] = 0

  • 위치 2에서 2만큼 이동해서 4 위치에 도달하는 방법은 0가지입니다.

[j][i]	0	1	2
0	1	0	0
1	0	1	0
2	0	0	1
3	0	1	1
4✅	0	1	0

최종 계산:

• 위치 4에 도달할 수 있는 모든 방법의 수를 더하면 dp[4][1] + dp[4][2] = 1 + 0 = 1입니다.

요약:

• DP 배열을 통해 각 위치에 도달할 수 있는 모든 방법의 수를 계산합니다.
• 각 단계에서 현재 위치에 도달할 수 있는 방법의 수를 이전 위치와 이동 거리에 따라 업데이트합니다.
• 마지막 목적지까지 도달할 수 있는 방법의 수를 모두 더해 최종 값을 구합니다.

전체 코드

class Solution {
    public int solution(int n, int k) {
        int MOD = 1_000_000_007; // 매우 큰 수가 나올 경우를 대비해 나머지 연산에 사용
        int[][] dp = new int[n + 1][k + 1]; // n: 목적지까지 거리 정수 값, k: 한 번에 이동할 수 있는 최대 거리 정수 값

        // 초기 값 설정
        dp[0][0] = 1;

        // DP 배열 채우기
        for (int j = 1; j <= n; j++) { // 목적지 위치 j에 대해
            for (int i = 1; i <= k; i++) { // 한 번에 이동할 수 있는 거리 i에 대해
                if (j >= i) { // 위치 j까지 i만큼 이동해서 도달할 수 있는 경우
                    // dp[j][i]는 j - i 위치에서 i만큼 이동한 모든 방법의 수를 더한 값
                    for (int m = 0; m <= k; m++) {
                        if (m != i) { // 연속된 같은 거리 이동을 피하기 위한 조건
                            dp[j][i] = (dp[j][i] + dp[j - i][m]) % MOD;
                        }
                    }
                }
            }
        }

        // 최종 목적지 n에 도달하는 모든 방법의 수를 계산
        int answer = 0;
        for (int i = 1; i <= k; i++) {
            answer = (answer + dp[n][i]) % MOD;
        }

        return answer;
    }
}