algorithm/DynamicProgramming/dp_night_dialer.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [문제]  \n",
    "#dynamic-programping\n",
    "\n",
    "![algorithm-problem.png](../../img/algorithm-231127-01.png)  \n",
    "![algorithm-problem.png](../../img/algorithm-231127-02.png)  \n",
    "link: https://leetcode.com/problems/knight-dialer  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [풀이]\n",
    "번호판 각 숫자에서 이동할 수 있는 숫자칸은 다음과 같다. \n",
    "\n",
    "```python\n",
    "dialMap = {\n",
    "    1:(6,8),\n",
    "    2:(7,9),\n",
    "    3:(4,8),\n",
    "    4:(0,3,9),\n",
    "    5:(),\n",
    "    6:(0,1,7),\n",
    "    7:(2,6),\n",
    "    8:(1,3),\n",
    "    9:(2,4),\n",
    "    0:(4,6),\n",
    "}\n",
    "```\n",
    "도착 다이얼(숫자) 입장에서 생각해보면, 현재 1에 도착한 말은 6이나 8에서 왔다고 할 수 있다. \n",
    "\n",
    "**(1) `n = 2` 일 때**  \n",
    "마지막 다이얼이 1인 경우의 수는 아래와 같다.  \n",
    "  (6, 1)  \n",
    "  (8, 1)  \n",
    "\n",
    "마지막 다이얼이 6인 경우의 수는 아래와 같다. --- (1)  \n",
    "  (0, 6)  \n",
    "  (1, 6)  \n",
    "  (7, 6)  \n",
    "   \n",
    "마지막 다이얼이 8인 경우의 수는 아래와 같다. --- (2)  \n",
    "  (1, 8)  \n",
    "  (3, 8)  \n",
    "\n",
    "**(2) `n = 3` 일 때**  \n",
    "마지막 다이얼이 1인 경우의 수는 경우의 수(1) + 경우의 수(2)와 같다.  \n",
    "  (0, 6), 1  \n",
    "  (1, 6), 1  \n",
    "  (7, 6), 1  --- (1)\n",
    "    \n",
    "  (1, 8), 1  \n",
    "  (3, 8), 1  --- (2)\n",
    "\n",
    "즉, `n=3, 마지막 다이얼이 1인 경우의 수`는 `n=2, 마지막 다이얼이 6인 경우의 수` + `n=2, 마지막 다이얼이 8인 경우의 수`이다. \n",
    "\n",
    "**일반화**  \n",
    "n = i, 마지막 다이얼이 dial인 경우의 수를 n(i, dial)라고 하면,  \n",
    "`n(i, dial) = sum(n(i-1, before_dial) for before_dial in dailMap[dial])` 라고 할 수 있다. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        x1 = x2 = x3 = x4 = x5 = x6 = x7 = x8 = x9 = x0 = 1\n",
    "        for i in range(n - 1):\n",
    "            x1, x2, x3, x4, x5, x6, x7, x8, x9, x0 = \\\n",
    "                x6 + x8, x7 + x9, x4 + x8, \\\n",
    "                x3 + x9 + x0, 0, x1 + x7 + x0, \\\n",
    "                x2 + x6, x1 + x3, x2 + x4, \\\n",
    "                x4 + x6\n",
    "        return (x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x0) % (10**9 + 7)"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}