chpt3_greedy.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "1f7a22e8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "260\n",
      "60\n",
      "10\n",
      "0\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "n = 1260\n",
    "count = 0\n",
    "\n",
    "coin_type = [500, 100, 50, 10]\n",
    "\n",
    "for coin in coin_type:\n",
    "    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기\n",
    "    n %= coin\n",
    "    print(n)\n",
    "    \n",
    "print(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ba2a0583",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 8 3\n",
      "2 4 5 4 6\n",
      "46\n"
     ]
    }
   ],
   "source": [
    "#92p 큰 수의 법칙 내가 쓴 답안\n",
    "\n",
    "N, M, K = map(int, input().split())\n",
    "num_list = list(map(int, input().split()))\n",
    "\n",
    "num_list.sort()\n",
    "tmpK = K\n",
    "sum = 0\n",
    "for i in range(M):\n",
    "    if(tmpK == 0):\n",
    "        sum+=num_list[N-2]\n",
    "        tmpK = K\n",
    "    else:\n",
    "        sum+=num_list[N-1]\n",
    "        tmpK-=1\n",
    "\n",
    "print(sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "e102619e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 8 3\n",
      "2 4 5 4 6\n",
      "46\n"
     ]
    }
   ],
   "source": [
    "# 책에서 나온 답안\n",
    "\n",
    "n, m, k = map(int, input().split())\n",
    "data = list(map(int, input().split()))\n",
    "\n",
    "data.sort()\n",
    "first = data[n-1]\n",
    "second = data[n-2]\n",
    "\n",
    "result = 0\n",
    "\n",
    "while True:\n",
    "    for i in range(k):\n",
    "        if m == 0:\n",
    "            break\n",
    "        result+=first\n",
    "        m-=1\n",
    "    if m == 0: break\n",
    "    result+=second\n",
    "    m-=1\n",
    "    \n",
    "print(result)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "6aaf4085",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 8 3\n",
      "2 4 5 4 6\n",
      "46\n"
     ]
    }
   ],
   "source": [
    "# 간단한 수학적 아이디어로 구현해보는 문제\n",
    "\n",
    "n, m, k = map(int, input().split())\n",
    "data = list(map(int, input().split()))\n",
    "data.sort()\n",
    "\n",
    "result = 0\n",
    "first = data[n-1]\n",
    "second = data[n-2]\n",
    "\n",
    "repeat_seq = first*k+second\n",
    "reps_len = k+1\n",
    "\n",
    "if m%reps_len == 0:\n",
    "    result = repeat_seq*(m//reps_len)\n",
    "else:\n",
    "    result = repeat_seq*(m//reps_len) + first*(m%reps_len)\n",
    "    \n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "5d35269e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 8 3\n",
      "2 4 5 4 6\n",
      "46\n"
     ]
    }
   ],
   "source": [
    "# 책에서 나온 답안 95p\n",
    "\n",
    "\n",
    "n, m, k = map(int, input().split())\n",
    "data = list(map(int, input().split()))\n",
    "data.sort()\n",
    "\n",
    "first = data[n-1]\n",
    "second = data[n-2]\n",
    " # 가장 큰 수가 더해지는 횟수 계산\n",
    "count = int(m/(k+1))*k\n",
    "count += m % (k+1)\n",
    "\n",
    "result = 0\n",
    "result+= count*first\n",
    "result+= (m-count)*second\n",
    "x\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "ca77e477",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 4\n",
      "7 3 1 8\n",
      "3 3 3 4\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# 숫자 카드 게임\n",
    "n, m = map(int, input().split())\n",
    "arr = [[]*m]*n\n",
    "\n",
    "for i in range(n):\n",
    "    arr[i] = list(map(int, input().split()))\n",
    "min = 0\n",
    "# 각 행의 최소값 중 가장 큰 것을 선택!\n",
    "for i in range(n):\n",
    "    arr_min = 10001\n",
    "    for j in range(m):\n",
    "        if arr_min >= arr[i][j]:\n",
    "            arr_min = arr[i][j]\n",
    "    if arr_min >= min:\n",
    "        min = arr_min\n",
    "print(min)\n",
    "# 내가 푼 내용"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "60a8d24c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 책에서 나온 코드\n",
    "# 1) min() 함수를 이용하는 답안 예시\n",
    "n, m = map(int, input().split())\n",
    "result = 0\n",
    "for i in range(n):\n",
    "    # 데이터 입력 받기\n",
    "    data = list(map(int, input().split()))\n",
    "    # 현재 줄에서 가장 작은 수 찾기\n",
    "    min_value = min(data)\n",
    "    # 가장 작은 수 중 가장 큰 수 찾기\n",
    "    result = max(result, min_value)\n",
    "    \n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "fa26918c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 3\n",
      "3 1 2\n",
      "4 1 4\n",
      "2 2 2\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# 2) 2중 반복문 구조를 이용하는 답안 예시\n",
    "n, m = map(int, input().split())\n",
    "\n",
    "result = 0\n",
    "for i in range(n):\n",
    "    data = list(map(int, input().split()))\n",
    "    \n",
    "    min_value = 10001\n",
    "    for a in data:\n",
    "        min_value = min(min_value, a)\n",
    "    \n",
    "    result = max(min_value, result)\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "05cae99e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25 3\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "# 1이 될 때까지\n",
    "n, k = map(int, input().split())\n",
    "\n",
    "count = 0\n",
    "while(True):\n",
    "    count += 1\n",
    "    \n",
    "    if n % k == 0: n//=k\n",
    "    else:\n",
    "        n-=1\n",
    "    if n==1: break\n",
    "\n",
    "print(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "db60c1de",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25 5\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# 단순하게 푸는 답안 예시\n",
    "n, k = map(int, input().split())\n",
    "result = 0\n",
    "\n",
    "# N이 K 이상이라면 K로 계속 나누기\n",
    "while n>=k:\n",
    "    # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기\n",
    "    while n % k != 0:\n",
    "        n-=1\n",
    "        result+=1\n",
    "    # K로 나누기\n",
    "    n //= k\n",
    "    result +=1\n",
    "    \n",
    "#마지막으로 남은 수에 대하여 1씩 빼기\n",
    "while n > 1:\n",
    "    n -= 1\n",
    "    result += 1\n",
    "\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "036187da",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25 5\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# 조금 더 효율적인 답안 예시\n",
    "\n",
    "# N, K를 공백으로 구분하여 입력받기\n",
    "n, k = map(int, input().split())\n",
    "result = 0\n",
    "\n",
    "while True:\n",
    "    # (N == K로 나누어 떨어지는 수)가 될 때까지 1씩 빼기\n",
    "    target = (n // k)*k\n",
    "    result += (n-target)\n",
    "    n = target\n",
    "    # N이 K보다 작을 때(더 이상 나눌 수 없을 때) 반복문 탈출\n",
    "    if n < k:\n",
    "        break\n",
    "    # K로 나누기\n",
    "    result += 1\n",
    "    n //= k\n",
    "    \n",
    "#마지막으로 남은 수에 대하여 1씩 빼기\n",
    "result += (n-1)\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f8942db7",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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
}