택배 상자가 들어오는 차례대로 트럭에 싣는다. 트럭 한 대에는 무게 합계가 C가 될 때까지 실을 수 있다.
상자마다 송장 번호, 갈 곳, 무게가 있다.
상자가 들어오면 다음 규칙으로 트럭을 고른다.
- 아직 떠나지 않은 트럭 가운데 갈 곳이 이 상자와 같고, 이 상자를 실어도 무게 합계가 C 이하인 트럭을 찾는다.
- 그런 트럭이 여럿이면 번호가 가장 작은 트럭에 싣는다. 남은 자리가 가장 크거나 작은 트럭이 아니다.
- 그런 트럭이 없으면 새 트럭을 하나 불러 싣는다. 트럭 번호는 불려 온 차례대로 1, 2, 3, …이고, 새 트럭의 갈 곳은 이 상자의 갈 곳이다.
- 상자를 실은 뒤 그 트럭의 무게 합계가 정확히 C가 되면 트럭은 곧바로 떠난다. 떠난 트럭에는 더 싣지 않는다.
모든 상자를 실은 뒤, 아직 떠나지 않은 트럭은 번호 순으로 떠난다.
첫 줄에 C와 상자 수 n, 다음 n줄에 "송장번호 갈곳 무게"가 빈칸 하나씩으로 나뉘어 들어온 차례대로 주어진다.
첫 줄에 트럭 수를 출력하라.
이어서 떠난 차례대로 트럭마다 한 줄에 "번호 갈곳 무게합계 상자수"와 그 트럭에 실은 송장 번호들을 실은 차례대로, 모두 빈칸 하나씩 띄워 출력하라.
상자 하나와 트럭 한 대를 각각 레코드(구조체)로 묶고, 트럭 레코드의 목록을 다뤄 보자.
입력
1 ≤ n ≤ 1,000, 1 ≤ C ≤ 1,000,000, 1 ≤ 무게 ≤ C(정수). 송장 번호는 영어 대문자와 숫자로 된 1~8글자이고 서로 다르다. 갈 곳은 영어 소문자 1~10글자다.
출력
트럭 수 한 줄, 이어서 트럭마다 한 줄
예시 1 · stdin
10 7
P1 seoul 6
P2 busan 4
P3 seoul 5
P4 busan 6
P5 seoul 4
P6 seoul 3
P7 seoul 5
stdout
4
2 busan 10 2 P2 P4
1 seoul 10 2 P1 P5
3 seoul 8 2 P3 P6
4 seoul 5 1 P7
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
트럭 한 대(번호, 갈 곳, 무게 합계, 송장 목록)를 묶는 법: Python @dataclass(목록 필드는 field(default_factory=list)), Java는 필드를 바꿀 수 있는 class(record는 필드를 못 바꿔요), C# class, C·C++ struct, JS·TS 객체 { no, dest, load, codes: [] }(TS는 interface Truck으로 모양을 적어요), 크레이콘은 클래스가 없어서 트럭마다 사전() 하나(t["load"], t["codes"])를 만들어 waiting.넣기(t)로 목록에 넣어요. 고른 트럭을 고칠 때가 핵심이에요. Python·JS·TS·Java·C# class·크레이콘 사전은 목록에서 꺼낸 값이 같은 트럭을 가리켜서 truck.load += w가 목록 안의 트럭을 바꿔요. C는 Truck *t = &trucks[k]처럼 포인터로, C++는 Truck &t = trucks[k]처럼 참조로 쥐어야 하고, C++ vector는 커질 때 칸을 옮겨서 쥐고 있던 참조가 깨지니 reserve를 하거나 자리 번호로 다시 찾아요. 떠난 트럭은 남은 트럭 목록에서 빼요: Python remove, JS·TS splice, Java·C# Remove, 크레이콘 자리빼기. 함정 다섯: ① load + w < C로 쓰면 딱 C가 되는 트럭을 못 고르고 새 트럭을 불러요. ② Python에서 def __init__(self, no, dest, codes=[])처럼 기본값을 []로 주면 그 목록 하나를 모든 트럭이 함께 써서 송장 번호가 섞여요(@dataclass는 이런 기본값을 아예 막아요). ③ C#에서 트럭을 struct로 만들면 Truck truck = waiting[at];이 복사본이라 Load를 고쳐도 목록 안은 그대로예요(C에서 Truck t = trucks[k];도 같아요). ④ 트럭 번호 순으로 출력하면 틀려요. 꽉 차서 먼저 떠난 트럭이 먼저예요. ⑤ 갈 곳이 같은 마지막 트럭 하나만 보면(next-fit) 앞 트럭에 남은 자리를 놓쳐요.
Pythonmain.py · 38 줄
import sysfrom dataclasses import dataclass, field@dataclassclass Truck: no: int dest: str load: int = 0 codes: list[str] = field(default_factory=list) # 트럭마다 새 목록def main(): data = sys.stdin.read().split() cap, n = int(data[0]), int(data[1]) trucks = 0 waiting: list[Truck] = [] # 아직 떠나지 않은 트럭(번호 순) departed: list[Truck] = [] # 떠난 차례 for i in range(n): code, dest, w = data[2 + 3 * i], data[3 + 3 * i], int(data[4 + 3 * i]) truck = next((t for t in waiting if t.dest == dest and t.load + w <= cap), None) if truck is None: trucks += 1 truck = Truck(trucks, dest) waiting.append(truck) truck.load += w truck.codes.append(code) if truck.load == cap: # 꽉 차면 곧바로 떠난다 waiting.remove(truck) departed.append(truck) departed.extend(waiting) # 남은 트럭은 번호 순으로 out = [str(len(departed))] for t in departed: out.append(f"{t.no} {t.dest} {t.load} {len(t.codes)} " + " ".join(t.codes)) print("\n".join(out))main()
JavaScriptmain.js · 27 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const cap = Number(data[0]);const n = Number(data[1]);let count = 0;const waiting = []; // 아직 떠나지 않은 트럭(번호 순)const departed = []; // 떠난 차례for (let i = 0; i < n; i++) { const code = data[2 + 3 * i]; const dest = data[3 + 3 * i]; const w = Number(data[4 + 3 * i]); let truck = waiting.find((t) => t.dest === dest && t.load + w <= cap); if (truck === undefined) { count++; truck = { no: count, dest, load: 0, codes: [] }; // 트럭마다 새 객체·새 배열 waiting.push(truck); } truck.load += w; truck.codes.push(code); if (truck.load === cap) { waiting.splice(waiting.indexOf(truck), 1); departed.push(truck); }}departed.push(...waiting);const out = [String(departed.length)];for (const t of departed) out.push(`${t.no} ${t.dest} ${t.load} ${t.codes.length} ${t.codes.join(" ")}`);console.log(out.join("\n"));
TypeScriptmain.ts · 34 줄
interface Truck { no: number; dest: string; load: number; codes: string[];}const data: string[] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const cap = Number(data[0]);const n = Number(data[1]);let count = 0;const waiting: Truck[] = []; // 아직 떠나지 않은 트럭(번호 순)const departed: Truck[] = []; // 떠난 차례for (let i = 0; i < n; i++) { const code = data[2 + 3 * i]; const dest = data[3 + 3 * i]; const w = Number(data[4 + 3 * i]); let truck: Truck | undefined = waiting.find((t) => t.dest === dest && t.load + w <= cap); if (truck === undefined) { count++; truck = { no: count, dest, load: 0, codes: [] }; waiting.push(truck); } truck.load += w; truck.codes.push(code); if (truck.load === cap) { waiting.splice(waiting.indexOf(truck), 1); departed.push(truck); }}departed.push(...waiting);const out: string[] = [String(departed.length)];for (const t of departed) out.push(`${t.no} ${t.dest} ${t.load} ${t.codes.length} ${t.codes.join(" ")}`);console.log(out.join("\n"));
JavaMain.java · 59 줄
import java.io.*;import java.util.*;public class Main { // 트럭 하나: 실은 상자가 늘어나니 record가 아니라 필드를 바꿀 수 있는 클래스 static class Truck { final int no; final String dest; int load = 0; final List<String> codes = new ArrayList<>(); Truck(int no, String dest) { this.no = no; this.dest = dest; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int cap = Integer.parseInt(st.nextToken()); int n = Integer.parseInt(st.nextToken()); int count = 0; List<Truck> waiting = new ArrayList<>(); List<Truck> departed = new ArrayList<>(); for (int i = 0; i < n; i++) { st = new StringTokenizer(br.readLine()); String code = st.nextToken(); String dest = st.nextToken(); int w = Integer.parseInt(st.nextToken()); Truck truck = null; for (Truck t : waiting) { if (t.dest.equals(dest) && t.load + w <= cap) { truck = t; break; } } if (truck == null) { truck = new Truck(++count, dest); waiting.add(truck); } truck.load += w; truck.codes.add(code); if (truck.load == cap) { waiting.remove(truck); departed.add(truck); } } departed.addAll(waiting); StringBuilder sb = new StringBuilder(); sb.append(departed.size()).append('\n'); for (Truck t : departed) { sb.append(t.no).append(' ').append(t.dest).append(' ').append(t.load).append(' ').append(t.codes.size()); for (String c : t.codes) sb.append(' ').append(c); sb.append('\n'); } System.out.print(sb); }}
C#Main.cs · 56 줄
using System;using System.Collections.Generic;using System.Text;// class라서 목록에서 꺼낸 t는 같은 트럭을 가리킨다(struct였다면 복사본)class Truck{ public int No; public string Dest; public int Load; public List<string> Codes = new List<string>(); public Truck(int no, string dest) { No = no; Dest = dest; }}class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int cap = int.Parse(data[0]); int n = int.Parse(data[1]); int count = 0; var waiting = new List<Truck>(); var departed = new List<Truck>(); for (int i = 0; i < n; i++) { string code = data[2 + 3 * i]; string dest = data[3 + 3 * i]; int w = int.Parse(data[4 + 3 * i]); Truck truck = waiting.Find(t => t.Dest == dest && t.Load + w <= cap); if (truck == null) { truck = new Truck(++count, dest); waiting.Add(truck); } truck.Load += w; truck.Codes.Add(code); if (truck.Load == cap) { waiting.Remove(truck); departed.Add(truck); } } departed.AddRange(waiting); var sb = new StringBuilder(); sb.Append(departed.Count).Append('\n'); foreach (var t in departed) sb.Append($"{t.No} {t.Dest} {t.Load} {t.Codes.Count} {string.Join(" ", t.Codes)}\n"); Console.Write(sb); }}
C++main.cpp · 57 줄
#include <iostream>#include <string>#include <vector>struct Truck { int no; std::string dest; int load = 0; std::vector<std::string> codes;};int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int cap, n; std::cin >> cap >> n; std::vector<Truck> trucks; trucks.reserve(n); // 상자마다 많아야 한 대: 자리를 미리 잡아 옮겨지지 않게 std::vector<int> waiting; // 아직 떠나지 않은 트럭의 자리(번호 순) std::vector<int> departed; // 떠난 차례 for (int i = 0; i < n; i++) { std::string code, dest; int w; std::cin >> code >> dest >> w; int pick = -1, at = -1; for (int k = 0; k < (int)waiting.size(); k++) { const Truck &t = trucks[waiting[k]]; if (t.dest == dest && t.load + w <= cap) { pick = waiting[k]; at = k; break; } } if (pick < 0) { trucks.push_back(Truck{(int)trucks.size() + 1, dest}); pick = (int)trucks.size() - 1; waiting.push_back(pick); at = (int)waiting.size() - 1; } Truck &t = trucks[pick]; // 참조라서 목록 안의 트럭이 바뀐다 t.load += w; t.codes.push_back(code); if (t.load == cap) { waiting.erase(waiting.begin() + at); departed.push_back(pick); } } departed.insert(departed.end(), waiting.begin(), waiting.end()); std::cout << departed.size() << '\n'; for (int k : departed) { const Truck &t = trucks[k]; std::cout << t.no << ' ' << t.dest << ' ' << t.load << ' ' << t.codes.size(); for (const auto &c : t.codes) std::cout << ' ' << c; std::cout << '\n'; } return 0;}
Cmain.c · 69 줄
#include <stdio.h>#include <string.h>#define MAXN 1000typedef struct { char code[9]; char dest[11]; int w; int next; /* 같은 트럭에 다음으로 실린 상자(없으면 -1) */} Parcel;typedef struct { int no; char dest[11]; int load; int count; int first, last; /* 실은 상자들의 첫·마지막 번호 */ int gone; /* 떠났으면 1 */} Truck;static Parcel parcels[MAXN];static Truck trucks[MAXN]; /* 상자마다 많아야 한 대 새로 생긴다 */static int order[MAXN]; /* 떠난 차례 */int main(void) { int cap, n, nt = 0, nd = 0; scanf("%d %d", &cap, &n); for (int i = 0; i < n; i++) { Parcel *p = &parcels[i]; scanf("%8s %10s %d", p->code, p->dest, &p->w); p->next = -1; Truck *t = NULL; /* 고른 트럭을 포인터로 쥐어야 목록 안의 트럭이 바뀐다 */ for (int k = 0; k < nt; k++) { if (!trucks[k].gone && strcmp(trucks[k].dest, p->dest) == 0 && trucks[k].load + p->w <= cap) { t = &trucks[k]; break; } } if (t == NULL) { t = &trucks[nt]; t->no = ++nt; strcpy(t->dest, p->dest); t->load = 0; t->count = 0; t->first = -1; t->gone = 0; } t->load += p->w; t->count++; if (t->first < 0) t->first = i; else parcels[t->last].next = i; t->last = i; if (t->load == cap) { t->gone = 1; order[nd++] = t->no - 1; } } for (int k = 0; k < nt; k++) if (!trucks[k].gone) order[nd++] = k; printf("%d\n", nd); for (int j = 0; j < nd; j++) { const Truck *t = &trucks[order[j]]; printf("%d %s %d %d", t->no, t->dest, t->load, t->count); for (int i = t->first; i >= 0; i = parcels[i].next) printf(" %s", parcels[i].code); printf("\n"); } return 0;}
Craykonmain.cray · 51 줄
// 크레이콘에는 클래스가 없어서 트럭 한 대를 사전 하나로 묶는다(no, dest, load, codes)첫줄 = 콘솔.수들읽기();cap = 첫줄[0];n = 첫줄[1];count = 0;waiting = []; // 아직 떠나지 않은 트럭(번호 순)departed = []; // 떠난 차례반복 (i = 0; i < n; i++){ p = 콘솔.줄읽기().공백제거().나누기(" "); code = p[0]; dest = p[1]; w = p[2].수로변환(); at = -1; 반복 (k = 0; k < waiting.개수; k++) { 만약 (waiting[k]["dest"] == dest && waiting[k]["load"] + w <= cap) { at = k; 그만; } } 만약 (at < 0) { count++; t = 사전(); // 트럭마다 새 사전, 새 목록 t["no"] = count; t["dest"] = dest; t["load"] = 0; t["codes"] = []; waiting.넣기(t); at = waiting.개수 - 1; } truck = waiting[at]; // 같은 사전을 가리킨다: 고치면 목록 안의 트럭이 바뀐다 truck["load"] = truck["load"] + w; truck["codes"].넣기(code); 만약 (truck["load"] == cap) { waiting.자리빼기(at); departed.넣기(truck); }}각각 (t 에서 waiting){ departed.넣기(t);}콘솔.쓰기(departed.개수);각각 (t 에서 departed){ 콘솔.쓰기(t["no"] + " " + t["dest"] + " " + t["load"] + " " + t["codes"].개수 + " " + t["codes"].잇기(" "));}