알고 스터디 다이나믹 프로그래밍.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 217p 1로 만들기"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|x|1|2|3|4|5|6|7|\n",
    "|---|------|---|---|---|---|---|---|\n",
    "| count |0|1|1|2|1|2|?|\n",
    "\n",
    "count[x] = min(\n",
    "\n",
    "count[x-1]+1, 1을 빼는 경우의 횟수\n",
    "\n",
    "count[x % ( 5 or 3 or 2 )] +1 )  5,3,2 로 나눠지는 경우의 횟수"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "26\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "x = int(input())\n",
    "\n",
    "count = [0] * (x + 1)\n",
    "\n",
    "for i in range(2, x + 1):  # 0,1은  0\n",
    "    minusOne = count[i - 1]\n",
    "    if i % 5 == 0:\n",
    "        count[i] = min(count[i // 5], minusOne) + 1\n",
    "    elif i % 3 == 0:\n",
    "        count[i] = min(count[i // 3], minusOne) + 1\n",
    "    elif i % 2 == 0:\n",
    "        count[i] = min(count[i // 2], minusOne) + 1\n",
    "    else:\n",
    "        count[i] = minusOne + 1\n",
    "\n",
    "print(count[x])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 220p 개미 전사"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "아무리 많은 창고가 있어도 마지막 창고를 기준으로 생각을하면\n",
    "마지막 창고 전 칸을 털었다면 마지막 칸을 털수 없고 털지 않았다면 마지막 칸을 털수 있다\n",
    "\n",
    "count[x] = min (count[x-1] , count[x-2] + 마지막 칸 )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "1 3 1 5\n",
      "[1, 3, 3, 8]\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "n = int(input())\n",
    "ban = list(map(int, input().split()))\n",
    "\n",
    "count = [0] * n\n",
    "\n",
    "count[0] = ban[0]\n",
    "count[1] = max(count[0], ban[1])\n",
    "\n",
    "for i in range(2, n):\n",
    "    count[i] = max(count[i - 1], count[i - 2] + ban[i])\n",
    "\n",
    "print(count[n - 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 223p 바닥공사"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "길이  n의 칸을 채우는 방법은\n",
    "\n",
    "n-1 의 길이의 칸에 세로로 긴 타일을 하나 놓는 방법과\n",
    "\n",
    "n-2 의 길이의 칸에 22 타일 하나를 놓거나 가로로 긴타일 2개를 놓는 방법이 있다 (세로로 긴타일 2개는 위 방법과 중복)\n",
    "\n",
    "count[n] = count[n-1] + ( count[n-2] * 2 )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "n = int(input())\n",
    "\n",
    "count = [0] * (n + 1)\n",
    "\n",
    "count[0] = 1\n",
    "count[1] = 1\n",
    "\n",
    "for i in range(2, n + 1):\n",
    "    count[i] = count[i - 1] + (2 * count[i - 2])\n",
    "\n",
    "print(count[n] % 796796)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}