자전거 대여소에 자전거가 n대 있고 1번부터 n번까지 번호가 붙어 있다.
i번 자전거는 지금까지 wᵢ만큼 달렸다.
손님 q명이 차례로 온다. 손님은 한 명씩 오고, 앞 손님이 자전거를 돌려준 다음에 다음 손님이 온다.
대여소는 손님이 올 때마다 남아 있는 자전거 가운데 달린 거리가 가장 짧은 자전거를 빌려준다.
달린 거리가 같은 자전거가 여럿이면 번호가 가장 작은 자전거를 빌려준다.
j번째 손님은 dⱼ만큼 타고 돌려주며, 그 자전거의 달린 거리는 dⱼ만큼 늘어난다.
돌려받은 자전거의 달린 거리가 L 이상이면 그 자전거는 정비소로 보내고 다시는 빌려주지 않는다.
손님이 왔을 때 남아 있는 자전거가 한 대도 없으면 그 손님은 자전거를 빌리지 못한다.
손님마다 한 줄에 빌려 간 자전거의 번호를 출력하라. 빌리지 못한 손님은 0을 출력한다.
마지막 줄에 정비소로 보낸 자전거의 수를 출력하라.
입력
첫 줄에 n, q, L이 빈칸 하나로 나뉘어 주어진다. 둘째 줄에 w₁ … wₙ, 셋째 줄에 d₁ … d_q가 빈칸 하나로 나뉘어 주어진다. 1 ≤ n ≤ 10,000, 1 ≤ q ≤ 10,000, 1 ≤ L ≤ 1,000,000,000,000, 0 ≤ wᵢ < L, 1 ≤ dⱼ ≤ 1,000,000,000. 모두 정수다
출력
손님마다 한 줄씩 q줄에 자전거 번호(빌리지 못하면 0), 이어서 한 줄에 정비소로 보낸 자전거의 수
예시 1 · stdin
3 7 10
4 2 2
3 3 5 4 2 6 1
stdout
2
3
1
2
3
3
1
2
예시 2 · stdin
1 3 5
0
5 1 1
stdout
1
0
0
1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
가장 작은 것을 꺼내고, 값을 바꿔서 다시 넣는 일을 되풀이할 때 쓰는 것이 힙(우선순위 큐)이에요. 손님마다 자전거를 다 훑으면 n × q번이지만 힙은 한 번에 log n번쯤이면 돼요. 첫 예시에서 넷째 손님 때 2번과 3번이 둘 다 5라서 2번이 나가고, 일곱째 손님이 탄 1번은 9 + 1 = 10으로 딱 L이 되어 정비소로 가요. 함정 하나: 거리가 같으면 번호가 작은 자전거예요. 힙은 같은 값끼리의 차례를 지켜 주지 않으니 번호까지 넣어서 견줘야 해요. Python은 heapq에 (거리, 번호) 튜플을, C++는 priority_queue에 pair를 넣으면 앞에서부터 견줘요. C++의 priority_queue는 큰 것이 먼저라 greater를 줘야 작은 것이 먼저 나와요. C#은 PriorityQueue<int, (long, int)>처럼 우선순위를 튜플로 줘요. 함정 둘: Java PriorityQueue의 비교 함수를 (int) (a[0] - b[0])처럼 뺄셈으로 쓰면 틀려요. 거리의 차가 21억을 넘으면 int로 자를 때 부호가 뒤집혀요. Long.compare를 써요. 함정 셋: 거리는 1조를 넘을 수 있어서 C·C++는 long long, Java·C#은 long이 필요해요. int에 담으면 값이 망가져요. Python은 정수에 한계가 없고, JavaScript·TypeScript·크레이콘의 수는 2^53(약 9천조)까지 정확해서 그대로 써도 돼요. 함정 넷: L 이상이에요. 딱 L이 된 자전거도 정비소로 가요. 함정 다섯: 처음에 한 번 정렬해 두고 그 차례로 돌아가며 빌려주면 틀려요. 타고 나면 거리가 달라져 차례가 바뀌어요. 함정 여섯: 자전거가 다 떨어질 수 있어요. 빈 힙에서 꺼내기 전에 비었는지 봐야 해요. Python heappop은 IndexError, Java poll은 null, C++ top은 정해지지 않은 동작이고, C#은 TryDequeue가 false를 돌려줘요. JavaScript·TypeScript·C·크레이콘에는 힙이 없어서 배열로 직접 만들어요. 이 풀이들은 힙에 번호만 넣고, 견줄 때 거리 배열을 들여다봐요. 힙 안에 있는 자전거의 거리는 바꾸지 않고, 꺼낸 다음에 거리를 바꾸고 다시 넣기 때문에 힙이 흐트러지지 않아요. 크레이콘은 목록에 넣기로 넣어 위로 올리고, 맨 끝을 자리빼기로 빼서 맨 위에 놓고 아래로 내려요.
Pythonmain.py · 26 줄
import heapqimport sysdata = sys.stdin.read().split()n, q, limit = int(data[0]), int(data[1]), int(data[2])# 힙에 (달린 거리, 번호) 튜플을 넣는다: 튜플은 앞에서부터 견주니 거리가 같으면 번호가 작은 것이 위로 온다heap = [(int(data[3 + i]), i + 1) for i in range(n)]heapq.heapify(heap)out = []repaired = 0for j in range(q): d = int(data[3 + n + j]) if not heap: # 빌려줄 자전거가 없다 out.append("0") continue dist, bike = heapq.heappop(heap) out.append(str(bike)) dist += d if dist >= limit: # 딱 L이 되어도 정비소로 간다 repaired += 1 else: heapq.heappush(heap, (dist, bike))out.append(str(repaired))print("\n".join(out))
JavaScriptmain.js · 58 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q, limit] = data;// JavaScript에는 힙이 없어서 직접 만든다. dist[b] = b번 자전거가 달린 거리, heap에는 번호만 넣는다const dist = [0, ...data.slice(3, 3 + n)];// a번이 b번보다 먼저 나가야 하는가: 거리가 짧은 쪽, 같으면 번호가 작은 쪽const before = (a, b) => dist[a] < dist[b] || (dist[a] === dist[b] && a < b);const heap = [];function push(b) { heap.push(b); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (!before(heap[i], heap[parent])) break; [heap[i], heap[parent]] = [heap[parent], heap[i]]; i = parent; }}function pop() { const top = heap[0]; const last = heap.pop(); if (heap.length > 0) { heap[0] = last; let i = 0; for (;;) { const l = 2 * i + 1; const r = l + 1; let first = i; if (l < heap.length && before(heap[l], heap[first])) first = l; if (r < heap.length && before(heap[r], heap[first])) first = r; if (first === i) break; [heap[i], heap[first]] = [heap[first], heap[i]]; i = first; } } return top;}for (let b = 1; b <= n; b++) push(b);const out = [];let repaired = 0;for (let j = 0; j < q; j++) { const d = data[3 + n + j]; if (heap.length === 0) { out.push(0); // 빌려줄 자전거가 없다 continue; } const bike = pop(); out.push(bike); dist[bike] += d; // 10^12 남짓이라 number로도 정확하다 if (dist[bike] >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else push(bike);}out.push(repaired);console.log(out.join("\n"));
TypeScriptmain.ts · 60 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q, limit] = data;// TypeScript에도 힙이 없어서 직접 만든다. dist[b] = b번 자전거가 달린 거리, heap에는 번호만 넣는다const dist: number[] = [0, ...data.slice(3, 3 + n)];// a번이 b번보다 먼저 나가야 하는가: 거리가 짧은 쪽, 같으면 번호가 작은 쪽const before = (a: number, b: number): boolean => dist[a] < dist[b] || (dist[a] === dist[b] && a < b);const heap: number[] = [];function push(b: number): void { heap.push(b); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (!before(heap[i], heap[parent])) break; [heap[i], heap[parent]] = [heap[parent], heap[i]]; i = parent; }}function pop(): number { const top = heap[0]; const last = heap.pop() as number; if (heap.length > 0) { heap[0] = last; let i = 0; for (;;) { const l = 2 * i + 1; const r = l + 1; let first = i; if (l < heap.length && before(heap[l], heap[first])) first = l; if (r < heap.length && before(heap[r], heap[first])) first = r; if (first === i) break; [heap[i], heap[first]] = [heap[first], heap[i]]; i = first; } } return top;}for (let b = 1; b <= n; b++) push(b);const out: number[] = [];let repaired = 0;for (let j = 0; j < q; j++) { const d = data[3 + n + j]; if (heap.length === 0) { out.push(0); // 빌려줄 자전거가 없다 continue; } const bike = pop(); out.push(bike); dist[bike] += d; // 10^12 남짓이라 number로도 정확하다 if (dist[bike] >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else push(bike);}out.push(repaired);console.log(out.join("\n"));
JavaMain.java · 36 줄
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); long limit = Long.parseLong(st.nextToken()); // 10^12까지라 long // {달린 거리, 번호}를 넣는다. 거리가 짧은 것, 같으면 번호가 작은 것이 먼저 — 뺄셈이 아니라 Long.compare로 견준다 PriorityQueue<long[]> heap = new PriorityQueue<>( (a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1])); st = new StringTokenizer(br.readLine()); for (int b = 1; b <= n; b++) heap.add(new long[] {Long.parseLong(st.nextToken()), b}); StringBuilder sb = new StringBuilder(); int repaired = 0; st = new StringTokenizer(br.readLine()); for (int j = 0; j < q; j++) { long d = Long.parseLong(st.nextToken()); if (heap.isEmpty()) { // 빌려줄 자전거가 없다 sb.append("0\n"); continue; } long[] top = heap.poll(); sb.append(top[1]).append('\n'); top[0] += d; if (top[0] >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else heap.add(top); } sb.append(repaired).append('\n'); System.out.print(sb); }}
C#Main.cs · 37 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), q = int.Parse(data[1]); long limit = long.Parse(data[2]); // 10^12까지라 long // PriorityQueue<값, 우선순위>: 우선순위가 작은 것이 먼저 나온다 // 우선순위를 (달린 거리, 번호) 튜플로 주면 거리가 같을 때 번호가 작은 것이 먼저다 var heap = new PriorityQueue<int, (long, int)>(); for (int b = 1; b <= n; b++) heap.Enqueue(b, (long.Parse(data[2 + b]), b)); var sb = new StringBuilder(); int repaired = 0; for (int j = 0; j < q; j++) { long d = long.Parse(data[3 + n + j]); // TryDequeue는 비어 있으면 false를 돌려준다: 빌려줄 자전거가 없다 if (!heap.TryDequeue(out int bike, out (long dist, int id) key)) { sb.Append("0\n"); continue; } sb.Append(bike).Append('\n'); long dist = key.dist + d; if (dist >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else heap.Enqueue(bike, (dist, bike)); } sb.Append(repaired).Append('\n'); Console.Write(sb); }}
C++main.cpp · 42 줄
#include <functional>#include <iostream>#include <queue>#include <utility>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; long long limit; // 10^12까지라 long long cin >> n >> q >> limit; // priority_queue는 기본이 큰 것 먼저다: greater를 주어 작은 것이 먼저 나오게 한다 // pair는 first부터 견주니 (달린 거리, 번호)로 넣으면 거리가 같을 때 번호가 작은 것이 먼저다 typedef pair<long long, int> Bike; priority_queue<Bike, vector<Bike>, greater<Bike>> heap; for (int b = 1; b <= n; b++) { long long w; cin >> w; heap.push({w, b}); } int repaired = 0; for (int j = 0; j < q; j++) { long long d; cin >> d; if (heap.empty()) { // 빌려줄 자전거가 없다 cout << "0\n"; continue; } Bike top = heap.top(); heap.pop(); cout << top.second << '\n'; top.first += d; if (top.first >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else heap.push(top); } cout << repaired << '\n'; return 0;}
Cmain.c · 69 줄
#include <stdio.h>#include <stdlib.h>// C에는 힙이 없어서 직접 만든다. dist[b] = b번 자전거가 달린 거리, heap에는 번호만 넣는다static long long *dist;static int *heap;static int size = 0;// a번이 b번보다 먼저 나가야 하는가: 거리가 짧은 쪽, 같으면 번호가 작은 쪽static int before(int a, int b) { return dist[a] < dist[b] || (dist[a] == dist[b] && a < b);}static void push(int b) { int i = size++; heap[i] = b; while (i > 0) { int parent = (i - 1) / 2; if (!before(heap[i], heap[parent])) break; int t = heap[i]; heap[i] = heap[parent]; heap[parent] = t; i = parent; }}static int pop(void) { int top = heap[0]; heap[0] = heap[--size]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, first = i; if (l < size && before(heap[l], heap[first])) first = l; if (r < size && before(heap[r], heap[first])) first = r; if (first == i) break; int t = heap[i]; heap[i] = heap[first]; heap[first] = t; i = first; } return top;}int main(void) { int n, q; long long limit; // 10^12까지라 int에는 안 든다 if (scanf("%d %d %lld", &n, &q, &limit) != 3) return 0; dist = malloc((n + 1) * sizeof(long long)); heap = malloc((n + 1) * sizeof(int)); for (int b = 1; b <= n; b++) { scanf("%lld", &dist[b]); push(b); } int repaired = 0; for (int j = 0; j < q; j++) { long long d; scanf("%lld", &d); if (size == 0) { // 빌려줄 자전거가 없다 printf("0\n"); continue; } int bike = pop(); printf("%d\n", bike); dist[bike] += d; if (dist[bike] >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else push(bike); } printf("%d\n", repaired); free(dist); free(heap); return 0;}
Craykonmain.cray · 94 줄
// 크레이콘에는 힙이 없어서 직접 만든다. dist[b] = b번 자전거가 달린 거리, heap에는 번호만 넣는다(번호는 0부터)첫줄 = 콘솔.수들읽기();n = 첫줄[0];q = 첫줄[1];limit = 첫줄[2];dist = 콘솔.수들읽기();타는거리 = 콘솔.수들읽기();heap = [];// a번이 b번보다 먼저 나가야 하는가: 거리가 짧은 쪽, 같으면 번호가 작은 쪽먼저인가(a, b){ 돌려주기 dist[a] < dist[b] || dist[a] == dist[b] && a < b;}힙넣기(b){ heap.넣기(b); i = heap.개수 - 1; 동안 (i > 0) { 부모 = 수학.몫(i - 1, 2); 만약 (!먼저인가(heap[i], heap[부모])) { 그만; } t = heap[i]; heap[i] = heap[부모]; heap[부모] = t; i = 부모; }}힙빼기(){ top = heap[0]; heap[0] = heap[heap.개수 - 1]; heap.자리빼기(heap.개수 - 1); i = 0; 동안 (참) { l = 2 * i + 1; r = l + 1; first = i; 만약 (l < heap.개수 && 먼저인가(heap[l], heap[first])) { first = l; } 만약 (r < heap.개수 && 먼저인가(heap[r], heap[first])) { first = r; } 만약 (first == i) { 그만; } t = heap[i]; heap[i] = heap[first]; heap[first] = t; i = first; } 돌려주기 top;}반복 (b = 0; b < n; b++){ 힙넣기(b);}out = [];repaired = 0;각각 (d 에서 타는거리){ 만약 (heap.개수 == 0) { out.넣기(0); // 빌려줄 자전거가 없다 } 아니면 { bike = 힙빼기(); out.넣기(bike + 1); dist[bike] += d; 만약 (dist[bike] >= limit) { repaired += 1; } 아니면 { 힙넣기(bike); } }}콘솔.쓰기(out.잇기("\n"));콘솔.쓰기(repaired);