Backjoon_12865.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Backjoon_12865.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyOp6i5A8Iv2OxjNIAKu0oXO",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/ynkim0/study/blob/main/Backjoon_12865.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "meXwHSVbFMIg",
        "outputId": "e5fc343b-a027-4f30-a06c-9aa90887a459"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "4 7\n",
            "6 13\n",
            "4 8\n",
            "3 6\n",
            "5 12\n",
            "14\n"
          ]
        }
      ],
      "source": [
        "n, k = map(int, input().split()) # 물건의 수, 용량\n",
        "\n",
        "thing = [[0,0]] # [물건의 무게, 물건의 가치]로 구성된 배열, 첫 번째 물건을 넣지 않을 때를 대비해 첫 항은 [0, 0]으로 함\n",
        "d = [[0]*(k+1) for _ in range(n+1)] # k+1개의 열(무게가 0 ~ k일때)과 n개의 행(각 물건에 관해)에 최대 가치를 표시\n",
        "\n",
        "for i in range(n):\n",
        "    thing.append(list(map(int, input().split()))) # 물건의 무게, 물건의 가치\n",
        "\n",
        "for i in range(1, n+1):\n",
        "    for j in range(1, k+1):\n",
        "        w = thing[i][0] # 물건의 무게\n",
        "        v = thing[i][1] # 물건의 가치\n",
        "\n",
        "        if j < w: # 더 넣을 수 있는 배낭의 용량 < 물건의 무게\n",
        "            d[i][j] = d[i-1][j] # 물건을 넣지 않는다\n",
        "        else: # 물건을 넣을 수 있을 경우\n",
        "            d[i][j] = max(d[i-1][j], d[i-1][j-w]+v) # 물건을 넣지 않을 때의 가치와 물건을 넣었을 때의 가치를 비교하여 큰 것을 사용\n",
        "\n",
        "print(d[n][k])"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# 출처 : https://hongcoding.tistory.com/50"
      ],
      "metadata": {
        "id": "WzIaj_l7GMMJ"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}