빵집에서 하루 동안 일어난 사건 q개가 일어난 차례대로 주어진다.
사건은 두 가지다.
"bake t e c"는 시각 t에 빵 c개를 한 묶음으로 구웠고, 이 빵들은 시각 e까지(e 포함) 팔 수 있다는 뜻이다.
"buy t k"는 시각 t에 손님 한 명이 빵 k개를 사러 왔다는 뜻이다.
손님이 오면 빵집은 그 시각에 팔 수 있는 빵, 곧 e ≥ t인 빵만 판다.
팔 수 있는 빵 가운데 기한 e가 가장 이른 빵부터 차례로 k개를 내준다.
한 묶음에서 일부만 팔 수도 있고, 남은 빵은 같은 기한으로 계속 남는다.
팔 수 있는 빵이 k개보다 적으면 있는 빵을 모두 내준다.
기한이 같은 빵끼리는 어느 것을 먼저 내줘도 답이 같다.
같은 시각의 사건은 입력에 적힌 차례대로 일어난다.
buy 사건마다 한 줄에, 손님이 받은 빵의 수와 받은 빵마다 (e − t)를 더한 값(남은 기한의 합)을 빈칸으로 나눠 출력하라.
받은 빵이 없으면 "0 0"을 출력한다.
입력
첫 줄에 q, 다음 q줄에 사건이 하나씩 주어진다. 1 ≤ q ≤ 10,000, 0 ≤ t ≤ e ≤ 1,000,000,000, 1 ≤ c, k ≤ 1,000,000. 사건의 t는 줄어들지 않고, buy 사건이 하나 이상 있다.
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
빵 묶음을 기한 e를 열쇠로 하는 최소 힙에 넣으면 늘 맨 위(가장 이른 기한)부터 팔 수 있어요. 기한이 지난 묶음은 미리 찾아 지우지 않고, 손님이 왔을 때 맨 위에서 e < t인 것을 꺼내 버리면 돼요(게으른 삭제) — 시각이 줄어들지 않으니 한 번 지난 묶음은 다시 팔 수 없어요. 묶음 하나는 빵을 낱개로 넣지 않고 [기한, 남은 개수] 한 칸으로 둬요(c가 100만이라 낱개로 넣으면 너무 많아요). 일부만 팔면 개수만 줄이면 되는데, 기한(열쇠)은 그대로라 힙 차례가 깨지지 않아요. 함정 하나: 기한 당일(e == t)에도 팔 수 있어요 — e <= t를 버리면 틀려요. 함정 둘: 최대 힙이면 기한이 늦은 빵부터 나가요. 예시의 첫 손님은 최소 힙이면 "4 4", 최대 힙이면 "4 6"이에요. C++ std::priority_queue는 기본이 최대 힙이라 std::greater<std::pair<long long, long long>>를 줘야 하고, top()은 고칠 수 없어서 꺼낸 뒤 남은 개수로 다시 넣어요. 함정 셋: 일부만 판 묶음을 통째로 꺼내 버리면 남은 빵이 사라져요. 함정 넷: 남은 기한의 합은 100만 × 10억 = 10^15까지 가서 32비트 int(약 21억)를 넘어요. C·C++ long long, Java·C# long이 필요하고, Python 정수는 끝이 없고, JavaScript·TypeScript·크레이콘의 수는 배정밀도 실수라 2^53(약 9×10^15)까지 정확해서 그대로 돼요. 힙은 언어마다 달라요: Python heapq는 목록 [기한, 개수]를 앞 칸부터 비교해 그대로 되고 heap[0][1]을 고쳐도 돼요, Java PriorityQueue<long[]>는 비교 함수 (x, y) -> Long.compare(x[0], y[0])를 주고 peek()으로 본 배열을 고쳐요, C# PriorityQueue<long[], long>은 값과 우선순위(기한)를 따로 넣고 TryPeek으로 둘 다 봐요. JavaScript·TypeScript·C·크레이콘은 힙이 없어 목록(배열)으로 직접 만들어요: i의 부모는 (i - 1) / 2(정수 나눗셈 — 크레이콘 수학.몫(i - 1, 2)), 자식은 2i + 1·2i + 2. 크레이콘은 줄을 콘솔.줄읽기().공백제거().나누기(" ")로 나누고 낱말을 .수로변환()으로 바꿔요. 힙의 칸은 bake 사건 수(10,000개 미만)를 넘지 않아 목록 한도 안이에요.
Pythonmain.py · 31 줄
import heapqimport syslines = sys.stdin.read().split("\n")q = int(lines[0])heap = [] # [기한, 남은 개수]: 기한이 가장 이른 묶음이 heap[0]out = []for line in lines[1 : 1 + q]: w = line.split() t = int(w[1]) if w[0] == "bake": heapq.heappush(heap, [int(w[2]), int(w[3])]) continue need = int(w[2]) got = 0 total = 0 # 받은 빵마다 (기한 - t)를 더한 값 while need > 0 and heap: e, c = heap[0] if e < t: # 기한이 지난 묶음은 버린다(e == t이면 아직 팔 수 있다) heapq.heappop(heap) continue take = min(c, need) got += take total += take * (e - t) need -= take if take == c: heapq.heappop(heap) else: heap[0][1] = c - take # 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 out.append(f"{got} {total}")print("\n".join(out))
JavaScriptmain.js · 75 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const q = Number(lines[0]);// 최소 힙: 칸마다 [기한, 남은 개수]. heap[0]이 기한이 가장 이른 묶음이고, i의 자식은 2i+1, 2i+2class MinHeap { constructor() { this.items = []; } get size() { return this.items.length; } top() { return this.items[0]; } push(x) { const a = this.items; a.push(x); let i = a.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (a[parent][0] <= a[i][0]) break; [a[parent], a[i]] = [a[i], a[parent]]; i = parent; } } pop() { const a = this.items; const top = a[0]; const last = a.pop(); if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let small = i; if (l < a.length && a[l][0] < a[small][0]) small = l; if (r < a.length && a[r][0] < a[small][0]) small = r; if (small === i) break; [a[small], a[i]] = [a[i], a[small]]; i = small; } } return top; }}const heap = new MinHeap();const out = [];for (let i = 1; i <= q; i++) { const w = lines[i].trim().split(" "); const t = Number(w[1]); if (w[0] === "bake") { heap.push([Number(w[2]), Number(w[3])]); continue; } let need = Number(w[2]); let got = 0; let total = 0; // 받은 빵마다 (기한 - t)를 더한 값: 10^15까지라 배정밀도 수로도 정확하다 while (need > 0 && heap.size > 0) { const batch = heap.top(); const [e, c] = batch; if (e < t) { // 기한이 지난 묶음은 버린다(e === t이면 아직 팔 수 있다) heap.pop(); continue; } const take = Math.min(c, need); got += take; total += take * (e - t); need -= take; if (take === c) heap.pop(); else batch[1] = c - take; // 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 } out.push(`${got} ${total}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 81 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const q: number = Number(lines[0]);type Batch = [expiry: number, count: number];// 최소 힙: heap[0]이 기한이 가장 이른 묶음이고, i의 자식은 2i+1, 2i+2class MinHeap { private items: Batch[] = []; get size(): number { return this.items.length; } top(): Batch { return this.items[0]; } push(x: Batch): void { const a = this.items; a.push(x); let i = a.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (a[parent][0] <= a[i][0]) break; [a[parent], a[i]] = [a[i], a[parent]]; i = parent; } } pop(): Batch { const a = this.items; const top = a[0]; const last = a.pop()!; // size > 0일 때만 부른다 if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let small = i; if (l < a.length && a[l][0] < a[small][0]) small = l; if (r < a.length && a[r][0] < a[small][0]) small = r; if (small === i) break; [a[small], a[i]] = [a[i], a[small]]; i = small; } } return top; }}const heap = new MinHeap();const out: string[] = [];for (let i = 1; i <= q; i++) { const w: string[] = lines[i].trim().split(" "); const t: number = Number(w[1]); if (w[0] === "bake") { heap.push([Number(w[2]), Number(w[3])]); continue; } let need: number = Number(w[2]); let got = 0; let total = 0; // 받은 빵마다 (기한 - t)를 더한 값: 10^15까지라 number로도 정확하다 while (need > 0 && heap.size > 0) { const batch: Batch = heap.top(); const [e, c] = batch; if (e < t) { // 기한이 지난 묶음은 버린다(e === t이면 아직 팔 수 있다) heap.pop(); continue; } const take: number = Math.min(c, need); got += take; total += take * (e - t); need -= take; if (take === c) heap.pop(); else batch[1] = c - take; // 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 } out.push(`${got} ${total}`);}console.log(out.join("\n"));
JavaMain.java · 44 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(in.readLine().trim()); // {기한, 남은 개수}를 기한이 이른 것부터 꺼내는 최소 힙 PriorityQueue<long[]> heap = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0])); StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { StringTokenizer st = new StringTokenizer(in.readLine()); String kind = st.nextToken(); long t = Long.parseLong(st.nextToken()); if (kind.equals("bake")) { long e = Long.parseLong(st.nextToken()); long c = Long.parseLong(st.nextToken()); heap.add(new long[] {e, c}); continue; } long need = Long.parseLong(st.nextToken()); long got = 0; long total = 0; // 받은 빵마다 (기한 - t)를 더한 값: 10^15까지라 long이 필요하다 while (need > 0 && !heap.isEmpty()) { long[] batch = heap.peek(); if (batch[0] < t) { // 기한이 지난 묶음은 버린다(같은 시각이면 아직 팔 수 있다) heap.poll(); continue; } long take = Math.min(batch[1], need); got += take; total += take * (batch[0] - t); need -= take; if (take == batch[1]) heap.poll(); else batch[1] -= take; // 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 } out.append(got).append(' ').append(total).append('\n'); } System.out.print(out); }}
C#Main.cs · 44 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { int q = int.Parse(Console.ReadLine().Trim()); // PriorityQueue<값, 우선순위>: 우선순위(기한)가 이른 묶음부터 나온다. // 값은 남은 개수를 고칠 수 있게 길이 1짜리 배열로 둔다 var heap = new PriorityQueue<long[], long>(); var sb = new StringBuilder(); for (int i = 0; i < q; i++) { string[] w = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long t = long.Parse(w[1]); if (w[0] == "bake") { heap.Enqueue(new long[] { long.Parse(w[3]) }, long.Parse(w[2])); continue; } long need = long.Parse(w[2]); long got = 0; long total = 0; // 받은 빵마다 (기한 - t)를 더한 값: 10^15까지라 long이 필요하다 while (need > 0 && heap.TryPeek(out long[] left, out long e)) { if (e < t) // 기한이 지난 묶음은 버린다(같은 시각이면 아직 팔 수 있다) { heap.Dequeue(); continue; } long take = Math.Min(left[0], need); got += take; total += take * (e - t); need -= take; if (take == left[0]) heap.Dequeue(); else left[0] -= take; // 개수만 줄인다: 우선순위(기한)는 그대로다 } sb.Append(got).Append(' ').Append(total).Append('\n'); } Console.Write(sb.ToString()); }}
C++main.cpp · 45 줄
#include <algorithm>#include <iostream>#include <queue>#include <string>#include <utility>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int q; std::cin >> q; // (기한, 남은 개수): std::greater를 줘야 기한이 이른 것부터 나온다(기본은 최대 힙) using Batch = std::pair<long long, long long>; std::priority_queue<Batch, std::vector<Batch>, std::greater<Batch>> heap; std::string out; for (int i = 0; i < q; i++) { std::string kind; long long t; std::cin >> kind >> t; if (kind == "bake") { long long e, c; std::cin >> e >> c; heap.push({e, c}); continue; } long long need; std::cin >> need; long long got = 0, total = 0; // total: 받은 빵마다 (기한 - t)를 더한 값, 10^15까지 while (need > 0 && !heap.empty()) { auto [e, c] = heap.top(); heap.pop(); if (e < t) continue; // 기한이 지난 묶음은 버린다(같은 시각이면 아직 팔 수 있다) long long take = std::min(c, need); got += take; total += take * (e - t); need -= take; // top()은 고칠 수 없으니 꺼낸 뒤 남은 것을 다시 넣는다(기한이 같아 다시 맨 앞에 온다) if (take < c) heap.push({e, c - take}); } out += std::to_string(got) + " " + std::to_string(total) + "\n"; } std::cout << out; return 0;}
Cmain.c · 74 줄
#include <stdio.h>#include <string.h>#define MAXQ 10000/* 최소 힙: 칸마다 (기한, 남은 개수). heap_e[0]이 기한이 가장 이르다 */static long long heap_e[MAXQ], heap_c[MAXQ];static int heap_size = 0;static void heap_swap(int i, int j) { long long t = heap_e[i]; heap_e[i] = heap_e[j]; heap_e[j] = t; t = heap_c[i]; heap_c[i] = heap_c[j]; heap_c[j] = t;}static void heap_push(long long e, long long c) { int i = heap_size++; heap_e[i] = e; heap_c[i] = c; while (i > 0 && heap_e[(i - 1) / 2] > heap_e[i]) { heap_swap((i - 1) / 2, i); i = (i - 1) / 2; }}static void heap_pop(void) { heap_size--; heap_e[0] = heap_e[heap_size]; heap_c[0] = heap_c[heap_size]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, small = i; if (l < heap_size && heap_e[l] < heap_e[small]) small = l; if (r < heap_size && heap_e[r] < heap_e[small]) small = r; if (small == i) break; heap_swap(small, i); i = small; }}int main(void) { int q; if (scanf("%d", &q) != 1) return 0; for (int i = 0; i < q; i++) { char kind[8]; long long t; scanf("%7s %lld", kind, &t); if (strcmp(kind, "bake") == 0) { long long e, c; scanf("%lld %lld", &e, &c); heap_push(e, c); continue; } long long need, got = 0, total = 0; /* total: 받은 빵마다 (기한 - t)를 더한 값, 10^15까지 */ scanf("%lld", &need); while (need > 0 && heap_size > 0) { if (heap_e[0] < t) { /* 기한이 지난 묶음은 버린다(같은 시각이면 아직 팔 수 있다) */ heap_pop(); continue; } long long take = heap_c[0] < need ? heap_c[0] : need; got += take; total += take * (heap_e[0] - t); need -= take; if (take == heap_c[0]) heap_pop(); else heap_c[0] -= take; /* 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 */ } printf("%lld %lld\n", got, total); } return 0;}
Craykonmain.cray · 91 줄
// 최소 힙(목록 heap): 칸마다 [기한, 남은 개수]. heap[0]이 기한이 가장 이른 묶음이고, i의 자식은 2i+1, 2i+2힙넣기(heap, x){ heap.넣기(x); i = heap.개수 - 1; 동안 (i > 0) { 부모 = 수학.몫(i - 1, 2); 만약 (heap[부모][0] <= heap[i][0]) { 그만; } t = heap[부모]; heap[부모] = heap[i]; heap[i] = t; i = 부모; }}힙빼기(heap){ heap[0] = heap[heap.개수 - 1]; heap.자리빼기(heap.개수 - 1); i = 0; 동안 (참) { l = 2 * i + 1; r = l + 1; small = i; 만약 (l < heap.개수 && heap[l][0] < heap[small][0]) { small = l; } 만약 (r < heap.개수 && heap[r][0] < heap[small][0]) { small = r; } 만약 (small == i) { 그만; } t = heap[small]; heap[small] = heap[i]; heap[i] = t; i = small; }}q = 콘솔.줄읽기().공백제거().수로변환();heap = [];반복 (n = 0; n < q; n++){ w = 콘솔.줄읽기().공백제거().나누기(" "); t = w[1].수로변환(); 만약 (w[0] == "bake") { 힙넣기(heap, [w[2].수로변환(), w[3].수로변환()]); } 아니면 { need = w[2].수로변환(); got = 0; total = 0; // 받은 빵마다 (기한 - t)를 더한 값 동안 (need > 0 && heap.개수 > 0) { batch = heap[0]; e = batch[0]; c = batch[1]; 만약 (e < t) { 힙빼기(heap); } 아니면 { take = 수학.작은수(c, need); got += take; total += take * (e - t); need -= take; 만약 (take == c) { 힙빼기(heap); } 아니면 { batch[1] = c - take; // 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 } } } 콘솔.쓰기(got + " " + total); }}