chpt11_greedy_problem_review.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "51f63ddc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "2 3 1 2 2\n",
      "1\n",
      "2\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# Q1. Adventurer guild\n",
    "\n",
    "n = int(input())\n",
    "\n",
    "adv = list(map(int, input().split()))\n",
    "\n",
    "adv.sort()\n",
    "\n",
    "count = 1\n",
    "\n",
    "group_num = 0\n",
    "\n",
    "for i in range(len(adv)):\n",
    "    if count >= adv[i]:\n",
    "        count = 1\n",
    "        group_num+=1\n",
    "    else:\n",
    "        count+=1\n",
    "        \n",
    "print(group_num)\n",
    "# solve!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "fa755de5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2024\n",
      "16\n"
     ]
    }
   ],
   "source": [
    "# Q2. Multiply or plus\n",
    "\n",
    "s = input()\n",
    "\n",
    "result = 0\n",
    "\n",
    "\n",
    "for i in range(len(s)):\n",
    "    if result == 0:\n",
    "        result += int(s[i])\n",
    "    else:\n",
    "        if s[i] == '0' or s[i] == '1':\n",
    "            result += int(s[i])\n",
    "        else:\n",
    "            result *= int(s[i])\n",
    "            \n",
    "print(result)\n",
    "\n",
    "# solve!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "209b0f27",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "00010100\n",
      "3 2\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# Q3. String reversing\n",
    "\n",
    "s = input()\n",
    "\n",
    "cnt0 = 0\n",
    "cnt1 = 0\n",
    "flag = 0 if s[0] == '0' else 1\n",
    "\n",
    "for i in range(len(s)):\n",
    "    if s[i] == '0':\n",
    "        # 뒤에서부터 0이 나오고 있을 때\n",
    "        if flag == 0:\n",
    "            continue\n",
    "        # 1이 나오다가 0이 나왔을 경우\n",
    "        else:\n",
    "            cnt1 += 1\n",
    "            flag = 0\n",
    "    else:\n",
    "        # 뒤에서부터 1이 나오고 있을 때\n",
    "        if flag == 1:\n",
    "            continue\n",
    "        # 0이 나오다가 1이 나온 경우\n",
    "        else:\n",
    "            cnt0 += 1\n",
    "            flag = 1\n",
    "            \n",
    "if flag:\n",
    "    cnt1+=1\n",
    "else:\n",
    "    cnt0+=1\n",
    "\n",
    "print(cnt0, cnt1)\n",
    "print(min(cnt0, cnt1))\n",
    "        \n",
    "# solve!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "bc29da0b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "1 1 4 9\n",
      "1\n",
      "2\n",
      "3\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# Q4. Unable to making bill\n",
    "\n",
    "n = int(input())\n",
    "target = 1\n",
    "\n",
    "bill = list(map(int, input().split()))\n",
    "bill.sort()\n",
    "\n",
    "for i in bill:\n",
    "    print(target)\n",
    "    if target < i:\n",
    "        break\n",
    "    else:\n",
    "        target+=i\n",
    "        \n",
    "print(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "7f8afa19",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 3\n",
      "1 3 2 3 2\n",
      "[]\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "# Q5. Selecting balling ball\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "\n",
    "ball = [0]*(m+1)\n",
    "\n",
    "balls = list(map(int, input().split()))\n",
    "\n",
    "for b in balls:\n",
    "    ball[b]+=1\n",
    "    \n",
    "result = 0\n",
    "for i in range(len(ball)):\n",
    "    if ball[i] > 0:\n",
    "        result+=(ball[i]*(sum(ball[i+1:])))\n",
    "    \n",
    "print(result)\n",
    "\n",
    "# solve!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b4b743bd",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Q6. Muji's food eating broadcasting live\n",
    "import heapq\n",
    "\n",
    "def solution(food_times, k):\n",
    "    q = []\n",
    "    \n",
    "    for i in range(len(food_times)):\n",
    "        heapq.heappush((food_times[i], i+1))\n",
    "    \n",
    "    sum_value = 0 # 먹기 위해 사용한 시간\n",
    "    previous = 0 # 직전에 다 먹은 음식 시간\n",
    "    length = len(food_times) # 남은 음식의 개수\n",
    "    \n",
    "    # sum_value + (현재의 음식 시간 - 이전의 음식 시간) * 현재의 음식 개수와 k 비교\n",
    "    while sum_value+((q[0][0] - previous)*length) <= k:\n",
    "        now = heapq.heappop(q)[0]\n",
    "        sum_value += (now - previous)*length\n",
    "        length -= 1\n",
    "        previous = now\n",
    "    \n",
    "    result = sorted(q, key=lambda x: x[1])\n",
    "    return result[(k - sum_value)%length][1]\n",
    "\n",
    "food_times = list(map(int, input().split()))\n",
    "k = int(input())\n",
    "\n",
    "print(solution(food_times, k))"
   ]
  }
 ],
 "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.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}