16 그리디 알고리즘.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "aa7a2c84-a049-4272-8c4e-fcba68c4d393",
   "metadata": {},
   "source": [
    "# [11047 동전 0](https://www.acmicpc.net/problem/11047)\n",
    "- `문제` 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.\n",
    "- `입력`\n",
    "    - 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)\n",
    "    - 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)\n",
    "- `출력` 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.\n",
    "- `예제 입력 1`\n",
    "    - 10 4200\n",
    "    - 1\n",
    "    - 5\n",
    "    - 10\n",
    "    - 50\n",
    "    - 100\n",
    "    - 500\n",
    "    - 1000\n",
    "    - 5000\n",
    "    - 10000\n",
    "    - 50000\n",
    "- `예제 출력 1` 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "df27d23d-b7d6-4478-8484-8bb6cb181d5e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[50000, 10000, 5000, 1000, 500, 100, 50, 10, 5, 1]\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "# 241009 수 AM 12:15\n",
    "\n",
    "# N: 동전 종류, K: 동전의 합\n",
    "N, K = map(int, input().split())\n",
    "\n",
    "# 동전 종류 리스트로 받기\n",
    "coins = []\n",
    "for _ in range(N):\n",
    "    coins.append(int(input()))\n",
    "coins.sort(reverse = True)\n",
    "\n",
    "answer = 0\n",
    "for coin in coins:\n",
    "    if coin <= K:\n",
    "        answer += K//coin\n",
    "        K -= coin*(K//coin)\n",
    "print(answer)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b787f8d2-a100-40b9-ba24-b326c7e41de5",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "# [2875 대회 or 인턴](https://www.acmicpc.net/problem/2875)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "faaae43b-fc9b-4405-b782-df5c46863e91",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 6 10 3\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "# 241009 수 AM 12:46\n",
    "\n",
    "# N: 여학생 수, M: 남학생 수, K: 인턴쉽 필수 참여 인원\n",
    "N, M, K = map(int, input().split())\n",
    "\n",
    "students = N+M\n",
    "N_case = min(N//2, M)\n",
    "\n",
    "while True:\n",
    "    if students - (2*N_case + 1*N_case) >= K:\n",
    "        print(N_case)\n",
    "        break\n",
    "    else:\n",
    "        N_case -= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "875b0694-071d-4b7a-b2a5-b45e050033e3",
   "metadata": {},
   "source": [
    "# [11399 ATM](https://www.acmicpc.net/problem/11399)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "98f86ba8-71fa-4a56-88a8-27ba2fc52c0f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 3, 4]\n",
      "32\n"
     ]
    }
   ],
   "source": [
    "# 241009 수 AM 1:24\n",
    "\n",
    "N = int(input())\n",
    "P = map(int, input().split())\n",
    "P_list = sorted(list(P))\n",
    "\n",
    "answer = 0\n",
    "for i in range(1, N+1):\n",
    "    answer += sum(P_list[:i])\n",
    "print(answer)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.12.6"
  },
  "pj_metadata": {
   "output": {
    "general": {
     "output_error": false
    }
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}