[LeetCode] 935. Knight Dialer

https://leetcode.com/problems/knight-dialer/description/

Knight Dialer - LeetCode

leetcode - Knight Dialer

문제 유형 : 다이나믹 프로그래밍 / 부분합

문제 난이도 : Mediumㅛ

 

문제

The chess knight has a unique movement, it may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L). The possible movements of chess knight are shown in this diagaram:

A chess knight can move as indicated in the chess diagram below:

체스 의 나이트 말은 특정한 움직임을 가진다. 수직으로2칸-수평으로1칸 또는 수직으로1칸-수평으로2칸, 즉 L자모양으로 움직일 수있다.

We have a chess knight and a phone pad as shown below, the knight can only stand on a numeric cell (i.e. blue cell).

우리는 체스 나이트와 폰 패드가 있다. 체스 나이트는 숫자 셀 위에만 설 수 있다.

Given an integer n, return how many distinct phone numbers of length n we can dial.

You are allowed to place the knight on any numeric cell initially and then you should perform n - 1 jumps to dial a number of length n. All jumps should be valid knight jumps.

As the answer may be very large, return the answer modulo 10^9 + 7.

 

정수 n이 주어진다. n의길이를 가진 모든 가능한 독립된 조합의 수를 구하시오.

당신은 나이트를 어느 숫자 셀에서 시자해도 됩니다.

수가 커질 수 있으니, 10^9+7로 나누시오.

 

 

풀이

처음에는 재귀로 풀어보려고 했지만, 시간초과가 되고 말았다.

대신, dp[i][j]를 i길이의 j로 끝나는 조합의 수로 했다.

위의 사진을 보면 알 수 있듯이, dp[len][j 다음으로 추가가 가능한 수] += dp[len-1][j]이다.

이를 1e9+7에 유의하여 누적시키면, dp[n][0] ~ dp[n][9]에는 각각의 수로 끝나는 조합의 수가 담겨있다.

 

 

코드

C++

class Solution {
public:
    int knightDialer(int n) {
        if (n == 1) return 10;
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        
        const int MOD = 1e9 + 7;
        const vector<vector<int>> pad = {
            {4, 6},
            {6, 8},
            {7, 9},
            {4, 8},
            {0, 3, 9},
            {},
            {0, 1, 7},
            {2, 6},
            {1, 3},
            {2, 4}
        };

        // dp[length][endNum]
        vector<vector<int>> dp(n + 1, vector<int>(10, 0));
        for (int i = 0; i < 10; i++) {
            dp[1][i] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < pad[j].size(); k++) {
                    dp[i][pad[j][k]] = (dp[i][pad[j][k]] + dp[i - 1][j]) % MOD;
                }
            }
        }
    
        int sum = 0;
        for (int i = 0; i < 10; i++) {
            sum = (sum + dp[n][i]) % MOD;
        }
        return sum;
    }
};