[LeetCode] 935. Knight Dialer

https://leetcode.com/problems/knight-dialer/description/?envType=daily-question&envId=2023-11-27

Knight Dialer - LeetCode

Knight Dialer - Medium

 

체스에서 나이트는 가장 위 그림처럼 움직인다.

휴대폰 다이얼에 이 나이트를 배치할때, n번의 움직임으로 만들수 있는 번호의 가짓수를 구하는 문제. (첫 배치도 n에 포함)

 

예시에 나와있는대로 진행해보면, 이 다음 차례에 특정한 번호에 도달하기 위해서는 특정한 수에서 출발해야 하는 것을 볼 수 있다.

이를 이용해 dp 식을 만들어 해결하자.

 

또, 다이얼을 잘 살펴보면,

1번 3번, 5번, 9번끼리,

2번 8번끼리,

4번 6번끼리 대칭인 것을 볼 수 있다.

 

이 점도 활용하자.

 

 

class Solution {
public:
    int knightDialer(int n) {
        int MOD = 1000000007;
        int dp[2][5] = {};
        int ret = 0;
        for (int i=0; i<5; i++) dp[0][i] = 1;
        for (int i=0; i<n-1; i++) {
            dp[1][0] = 2*dp[0][4] % MOD;
            dp[1][1] = (dp[0][2] + dp[0][4]) % MOD;
            dp[1][2] = 2*dp[0][1] % MOD;
            dp[1][4] = ((2 * dp[0][1] % MOD) + dp[0][0]) % MOD;
            for (int j = 0; j<5; j++) dp[0][j] = dp[1][j];
        }
        for (int i=0; i<10; i++) ret = (ret + dp[0][i==3||i==7||i==9?1:i==8?2:i==6?4:i==5?3:i]) % MOD;
        return ret;
    }
};