요리법 n개가 주어진다. 요리법마다 요리 이름과 재료 줄 c개가 있고, 재료 줄은 재료 이름과 양이다.
양은 정수 "p" 또는 분수 "p/q"(p를 q로 나눈 값)로 적혀 있고, 분수는 약분되어 있지 않을 수 있다.
한 요리법에 같은 재료가 여러 줄 나오면 그 양을 모두 더한 것이 그 재료의 양이다.
두 요리법은 쓰는 재료의 모임이 똑같고, 어떤 양수 r이 있어 모든 재료에서 한쪽 양이 다른 쪽 양의 r배이면 비율이 같다.
비율이 같은 요리법끼리 한 묶음으로 묶어라.
묶음마다 비율을 가장 작은 양의 정수들로 나타낸다. 곧 묶음의 어느 요리법의 양과도 비율이 같고, 모두 양의 정수이며, 최대공약수가 1인 정수들이다.
첫 줄에 묶음의 수를 출력하라.
이어서 묶음마다 한 줄에, 재료를 이름의 문자열 차례(글자 코드 차례로, 숫자가 영어 소문자보다 앞)로 "재료:정수"를 빈칸 하나씩 띄워 쓰고, 그 뒤에 " = "과 그 묶음의 요리 이름들을 입력에 나온 차례대로 빈칸 하나씩 띄워 출력하라.
묶음은 그 묶음의 요리 가운데 입력에서 가장 먼저 나온 요리의 차례대로 출력한다.
입력
첫 줄에 n, 다음 n줄에 요리법마다 "이름 c 재료₁ 양₁ … 재료_c 양_c"가 빈칸 하나로 나뉘어 주어진다. 1 ≤ n ≤ 2,000, 1 ≤ c ≤ 10. 요리 이름과 재료 이름은 영어 소문자·숫자 1 ~ 10글자이고, 요리 이름은 서로 다르다. 양은 "p" 또는 "p/q"이고 1 ≤ p ≤ 1,000, 1 ≤ q ≤ 10인 정수다
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
묶기의 핵심은 '같은 묶음이면 똑같아지는 열쇠'를 만드는 거예요. 여기서는 그 열쇠가 바로 출력할 비율이에요: 재료마다 양을 분수로 더하고(a/b + p/q = (aq + pb)/(bq)를 약분), 분모들의 최소공배수를 곱해 정수로 만든 뒤, 그 정수들의 최대공약수로 나누면 가장 작은 정수 비가 돼요. 이 비를 재료 이름 차례로 늘어놓아 열쇠로 쓰면, 넣은 차례를 지키는 사전 하나로 묶음과 출력 차례가 한꺼번에 정해져요. 예시: bread는 flour 1/2 + 1/2 = 1, sugar 1/2라 ×2 하면 2:1, cake 200:100도 ÷100 하면 2:1이에요. 양은 재료 하나에 1,000 × 10줄 = 1만, 분모의 최소공배수는 많아야 2,520이라 2,520만으로 int 안이에요. 함정 하나: 이름 차례로 늘어놓지 않으면sugar 1 flour 2와 flour 4 sugar 2가 다른 열쇠가 돼요. 함정 둘: 같은 재료가 또 나올 때 더하지 않고 덮어쓰면 틀려요. 함정 셋: 양을 double로 더해 비를 실수로 견주면 1/10 + 2/10이 0.30000000000000004라 3/10과 다른 묶음이 돼요 — 분수 그대로(정수 둘로) 계산해요. 함정 넷: 열쇠를 이어 붙일 때 나누는 글자가 없으면b1:2 c:1과 b:12 c:1이 모두 b12c1이 돼요(이름에 숫자가 들어가요). 열쇠로 쓸 수 있는 것은 언어마다 달라요: Python은 튜플(목록은 해시가 안 돼서 열쇠가 못 돼요), Java는 List<String>(내용으로 equals·hashCode를 만들어요 — String[] 배열은 같은 객체일 때만 같아서 묶음이 하나도 안 생겨요), C++ std::map은 std::vector<std::pair<…>>를 내용으로 견줘 바로 열쇠로 써요, JavaScript·TypeScript·C#·크레이콘은 문자열로 만들어 써요(JS Map은 배열을 같은 객체일 때만 같게 봐요). 묶음이 나온 차례: Python dict·JS Map·Java LinkedHashMap·크레이콘 사전의 열쇠목록은 넣은 차례를 지키지만, Java HashMap은 차례가 제멋대로이고 C# Dictionary는 차례를 약속하지 않으니 나온 차례 목록을 따로 둬요. 분수 읽기도 달라요: Python Fraction("3/4")은 바로 되고, C sscanf(s, "%d/%d", &p, &q)는 "2"에서 1을 돌려줘요. C++ std::stoi("3/4")는 오류 없이 / 앞에서 멈춰 3을 줘서, 분모를 잊은 줄도 모르고 지나가요. 크레이콘은 나누기("/")로 잘라 수로변환()해요.
Pythonmain.py · 25 줄
import sysfrom fractions import Fractionfrom math import gcd, lcmlines = sys.stdin.read().split("\n")n = int(lines[0])groups = {} # 비율 열쇠(재료 이름 차례로 늘어놓은 (이름, 정수) 튜플) → 요리 이름들. dict는 넣은 차례를 지킨다for i in range(1, n + 1): parts = lines[i].split() name, c = parts[0], int(parts[1]) amount = {} # 재료 → 양(분수). 같은 재료가 또 나오면 더한다 for j in range(c): ing, q = parts[2 + 2 * j], parts[3 + 2 * j] amount[ing] = amount.get(ing, Fraction(0)) + Fraction(q) # Fraction("3/4")도, Fraction("2")도 된다 # 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 den = lcm(*(a.denominator for a in amount.values())) whole = {ing: int(a * den) for ing, a in amount.items()} g = gcd(*whole.values()) key = tuple(sorted((ing, v // g) for ing, v in whole.items())) # 이름 차례로 늘어놓아야 같은 비율이 같은 열쇠가 된다 groups.setdefault(key, []).append(name)out = [str(len(groups))]for key, names in groups.items(): out.append(" ".join(f"{ing}:{v}" for ing, v in key) + " = " + " ".join(names))print("\n".join(out))
JavaScriptmain.js · 37 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));const n = Number(lines[0]);const groups = new Map(); // 비율 열쇠(문자열) → 요리 이름들. Map은 넣은 차례를 지킨다for (let i = 1; i <= n; i++) { const parts = lines[i].trim().split(" "); const name = parts[0]; const c = Number(parts[1]); const amount = new Map(); // 재료 → [분자, 분모](약분해 둔다). 같은 재료가 또 나오면 더한다 for (let j = 0; j < c; j++) { const ing = parts[2 + 2 * j]; const [p, q = "1"] = parts[3 + 2 * j].split("/"); // "3/4" → 3, 4 / "2" → 2, 1 const [a, b] = amount.get(ing) ?? [0, 1]; let num = a * Number(q) + Number(p) * b; let den = b * Number(q); const g = gcd(num, den); amount.set(ing, [num / g, den / g]); } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 let lcm = 1; for (const [, den] of amount.values()) lcm = (lcm / gcd(lcm, den)) * den; const ings = [...amount.keys()].sort(); // 이름 차례로 늘어놓아야 같은 비율이 같은 열쇠가 된다 const whole = ings.map((ing) => { const [num, den] = amount.get(ing); return num * (lcm / den); }); const g = whole.reduce(gcd); const key = ings.map((ing, k) => `${ing}:${whole[k] / g}`).join(" "); // 빈칸과 :로 나눠야 b1:2와 b:12가 섞이지 않는다 if (!groups.has(key)) groups.set(key, []); groups.get(key).push(name);}const out = [String(groups.size)];for (const [key, names] of groups) out.push(`${key} = ${names.join(" ")}`);console.log(out.join("\n"));
TypeScriptmain.ts · 42 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const gcd = (a: number, b: number): number => (b === 0 ? a : gcd(b, a % b));type Frac = [num: number, den: number];const n = Number(lines[0]);const groups = new Map<string, string[]>(); // 비율 열쇠(문자열) → 요리 이름들. Map은 넣은 차례를 지킨다for (let i = 1; i <= n; i++) { const parts = lines[i].trim().split(" "); const name = parts[0]; const c = Number(parts[1]); const amount = new Map<string, Frac>(); // 재료 → [분자, 분모](약분해 둔다). 같은 재료가 또 나오면 더한다 for (let j = 0; j < c; j++) { const ing = parts[2 + 2 * j]; const [p, q = "1"] = parts[3 + 2 * j].split("/"); // "3/4" → 3, 4 / "2" → 2, 1 const [a, b] = amount.get(ing) ?? [0, 1]; const num = a * Number(q) + Number(p) * b; const den = b * Number(q); const g = gcd(num, den); amount.set(ing, [num / g, den / g]); } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 let lcm = 1; for (const [, den] of amount.values()) lcm = (lcm / gcd(lcm, den)) * den; const ings: string[] = [...amount.keys()].sort(); // 이름 차례로 늘어놓아야 같은 비율이 같은 열쇠가 된다 const whole: number[] = ings.map((ing) => { const [num, den] = amount.get(ing)!; return num * (lcm / den); }); const g = whole.reduce(gcd); const key = ings.map((ing, k) => `${ing}:${whole[k] / g}`).join(" "); // 빈칸과 :로 나눠야 b1:2와 b:12가 섞이지 않는다 const names = groups.get(key); if (names) names.push(name); else groups.set(key, [name]);}const out: string[] = [String(groups.size)];for (const [key, names] of groups) out.push(`${key} = ${names.join(" ")}`);console.log(out.join("\n"));
JavaMain.java · 45 줄
import java.io.*;import java.util.*;public class Main { static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); // 비율 열쇠 → 요리 이름들. LinkedHashMap은 넣은 차례를 지킨다(HashMap은 차례가 제멋대로) Map<List<String>, List<String>> groups = new LinkedHashMap<>(); for (int i = 0; i < n; i++) { String[] parts = br.readLine().trim().split(" "); String name = parts[0]; int c = Integer.parseInt(parts[1]); // 재료 → {분자, 분모}(약분해 둔다). TreeMap이라 이름 차례로 늘어선다 TreeMap<String, int[]> amount = new TreeMap<>(); for (int j = 0; j < c; j++) { String ing = parts[2 + 2 * j]; String[] pq = parts[3 + 2 * j].split("/"); int p = Integer.parseInt(pq[0]); int q = pq.length > 1 ? Integer.parseInt(pq[1]) : 1; int[] f = amount.getOrDefault(ing, new int[] {0, 1}); int num = f[0] * q + p * f[1], den = f[1] * q; // 같은 재료가 또 나오면 더한다 int g = gcd(num, den); amount.put(ing, new int[] {num / g, den / g}); } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 int lcm = 1; for (int[] f : amount.values()) lcm = lcm / gcd(lcm, f[1]) * f[1]; int g = 0; for (int[] f : amount.values()) g = gcd(g, f[0] * (lcm / f[1])); // 열쇠는 List<String>: List는 내용으로 equals·hashCode를 만든다(배열 String[]은 같은 객체일 때만 같다) List<String> key = new ArrayList<>(); for (Map.Entry<String, int[]> e : amount.entrySet()) key.add(e.getKey() + ":" + e.getValue()[0] * (lcm / e.getValue()[1]) / g); groups.computeIfAbsent(key, k -> new ArrayList<>()).add(name); } StringBuilder sb = new StringBuilder(); sb.append(groups.size()).append('\n'); for (Map.Entry<List<String>, List<String>> e : groups.entrySet()) sb.append(String.join(" ", e.getKey())).append(" = ").append(String.join(" ", e.getValue())).append('\n'); System.out.print(sb); }}
C#Main.cs · 52 줄
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ static int Gcd(int a, int b) => b == 0 ? a : Gcd(b, a % b); static void Main() { int n = int.Parse(Console.ReadLine()!.Trim()); // 비율 열쇠(문자열) → 요리 이름들. 넣은 차례를 따로 적어 둔다(Dictionary의 열거 차례는 약속되어 있지 않다) var groups = new Dictionary<string, List<string>>(); var order = new List<string>(); for (int i = 0; i < n; i++) { var parts = Console.ReadLine()!.Trim().Split(' '); string name = parts[0]; int c = int.Parse(parts[1]); // 재료 → (분자, 분모)(약분해 둔다). 같은 재료가 또 나오면 더한다 var amount = new SortedDictionary<string, (int Num, int Den)>(StringComparer.Ordinal); for (int j = 0; j < c; j++) { string ing = parts[2 + 2 * j]; var pq = parts[3 + 2 * j].Split('/'); int p = int.Parse(pq[0]); int q = pq.Length > 1 ? int.Parse(pq[1]) : 1; var (a, b) = amount.TryGetValue(ing, out var f) ? f : (0, 1); int num = a * q + p * b, den = b * q; int g = Gcd(num, den); amount[ing] = (num / g, den / g); } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 int lcm = amount.Values.Aggregate(1, (l, f) => l / Gcd(l, f.Den) * f.Den); int gAll = amount.Values.Aggregate(0, (g, f) => Gcd(g, f.Num * (lcm / f.Den))); // SortedDictionary라 이름 차례로 늘어선다. 빈칸과 :로 나눠야 b1:2와 b:12가 섞이지 않는다 string key = string.Join(" ", amount.Select(e => $"{e.Key}:{e.Value.Num * (lcm / e.Value.Den) / gAll}")); if (!groups.TryGetValue(key, out var names)) { names = new List<string>(); groups[key] = names; order.Add(key); } names.Add(name); } var sb = new StringBuilder(); sb.Append(groups.Count).Append('\n'); foreach (var key in order) sb.Append(key).Append(" = ").Append(string.Join(" ", groups[key])).Append('\n'); Console.Write(sb); }}
C++main.cpp · 56 줄
#include <iostream>#include <map>#include <numeric>#include <string>#include <utility>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; // 비율 열쇠 → 묶음 번호. 열쇠는 (재료, 정수) 쌍의 vector: std::map은 vector도 내용으로 견준다 std::map<std::vector<std::pair<std::string, int>>, int> index; std::vector<std::vector<std::pair<std::string, int>>> keys; // 묶음마다 열쇠(나온 차례대로) std::vector<std::vector<std::string>> names; for (int i = 0; i < n; i++) { std::string name; int c; std::cin >> name >> c; std::map<std::string, std::pair<int, int>> amount; // 재료 → (분자, 분모). std::map이라 이름 차례로 늘어선다 for (int j = 0; j < c; j++) { std::string ing, qs; std::cin >> ing >> qs; // std::stoi("3/4")는 '/' 앞에서 멈춰 3을 준다: 나눗셈 기호를 직접 찾아 자른다 auto slash = qs.find('/'); int p = std::stoi(qs.substr(0, slash)); int q = slash == std::string::npos ? 1 : std::stoi(qs.substr(slash + 1)); auto [it, fresh] = amount.try_emplace(ing, 0, 1); // 같은 재료가 또 나오면 더한다 auto &[num, den] = it->second; int nn = num * q + p * den, dd = den * q; int g = std::gcd(nn, dd); num = nn / g, den = dd / g; } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 int l = 1, g = 0; for (const auto &[ing, f] : amount) l = std::lcm(l, f.second); for (const auto &[ing, f] : amount) g = std::gcd(g, f.first * (l / f.second)); std::vector<std::pair<std::string, int>> key; for (const auto &[ing, f] : amount) key.emplace_back(ing, f.first * (l / f.second) / g); auto [it, fresh] = index.try_emplace(key, static_cast<int>(keys.size())); if (fresh) { keys.push_back(key); names.emplace_back(); } names[it->second].push_back(name); } std::cout << keys.size() << '\n'; for (size_t k = 0; k < keys.size(); k++) { for (size_t t = 0; t < keys[k].size(); t++) std::cout << (t ? " " : "") << keys[k][t].first << ':' << keys[k][t].second; std::cout << " ="; for (const auto &nm : names[k]) std::cout << ' ' << nm; std::cout << '\n'; }}
Cmain.c · 67 줄
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 2000#define MAXC 10#define KEYLEN 256 /* 재료 10개 × ("이름 10글자" + ":" + 수 8자리 + 빈칸) */typedef struct { char ing[11]; int num, den; /* 지금까지 더한 양(약분해 둔다) */} Item;static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }static int by_name(const void *x, const void *y) { return strcmp(((const Item *)x)->ing, ((const Item *)y)->ing); }static char keys[MAXN][KEYLEN]; /* 묶음마다 비율 열쇠(나온 차례대로) */static char names[MAXN][11]; /* 요리 이름 */static int group_of[MAXN]; /* 요리 → 묶음 번호 */int main(void) { int n, groups = 0; if (scanf("%d", &n) != 1) return 0; for (int i = 0; i < n; i++) { int c, k = 0; Item item[MAXC]; scanf("%10s %d", names[i], &c); for (int j = 0; j < c; j++) { char ing[11], qs[16]; int p, q = 1; scanf("%10s %15s", ing, qs); if (sscanf(qs, "%d/%d", &p, &q) < 2) q = 1; /* "2"는 2/1 */ int t = 0; while (t < k && strcmp(item[t].ing, ing) != 0) t++; /* 같은 재료가 또 나오면 더한다 */ if (t == k) { strcpy(item[k].ing, ing); item[k].num = 0, item[k].den = 1; k++; } int num = item[t].num * q + p * item[t].den, den = item[t].den * q; int g = gcd(num, den); item[t].num = num / g, item[t].den = den / g; } qsort(item, k, sizeof(Item), by_name); /* 이름 차례로 늘어놓아야 같은 비율이 같은 열쇠가 된다 */ /* 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 */ int lcm = 1, g = 0; for (int t = 0; t < k; t++) lcm = lcm / gcd(lcm, item[t].den) * item[t].den; for (int t = 0; t < k; t++) g = gcd(g, item[t].num * (lcm / item[t].den)); char key[KEYLEN]; int len = 0; for (int t = 0; t < k; t++) /* 빈칸과 :로 나눠야 b1:2와 b:12가 섞이지 않는다 */ len += snprintf(key + len, KEYLEN - len, "%s%s:%d", t ? " " : "", item[t].ing, item[t].num * (lcm / item[t].den) / g); int found = 0; while (found < groups && strcmp(keys[found], key) != 0) found++; /* 요리 2,000개라 앞에서부터 찾아도 빠르다 */ if (found == groups) strcpy(keys[groups++], key); group_of[i] = found; } printf("%d\n", groups); for (int g = 0; g < groups; g++) { printf("%s =", keys[g]); for (int i = 0; i < n; i++) if (group_of[i] == g) printf(" %s", names[i]); printf("\n"); } return 0;}
Craykonmain.cray · 72 줄
최대공약수(a, b){ 동안 (b != 0) { t = a % b; a = b; b = t; } 돌려주기 a;}n = 콘솔.줄읽기().공백제거().수로변환();groups = 사전(); // 비율 열쇠(문자열) → 요리 이름들. 사전의 열쇠목록은 넣은 차례를 지킨다반복 (i = 0; i < n; i++){ parts = 콘솔.줄읽기().공백제거().나누기(" "); name = parts[0]; c = parts[1].수로변환(); num = 사전(); // 재료 → 지금까지 더한 양의 분자(약분해 둔다). 같은 재료가 또 나오면 더한다 den = 사전(); // 재료 → 분모 반복 (j = 0; j < c; j++) { ing = parts[2 + 2 * j]; pq = parts[3 + 2 * j].나누기("/"); // "3/4" → ["3", "4"], "2" → ["2"] p = pq[0].수로변환(); q = 1; 만약 (pq.개수 > 1) { q = pq[1].수로변환(); } 만약 (!num.있나(ing)) { num[ing] = 0; den[ing] = 1; } a = num[ing] * q + p * den[ing]; b = den[ing] * q; g = 최대공약수(a, b); num[ing] = a / g; den[ing] = b / g; } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 ings = num.열쇠목록; ings.정렬(); // 이름 차례로 늘어놓아야 같은 비율이 같은 열쇠가 된다 lcm = 1; 각각 (x 에서 ings) { lcm = lcm / 최대공약수(lcm, den[x]) * den[x]; } g = 0; 각각 (x 에서 ings) { g = 최대공약수(g, num[x] * (lcm / den[x])); } 조각 = []; 각각 (x 에서 ings) { 조각.넣기(x + ":" + num[x] * (lcm / den[x]) / g); // 빈칸과 :로 나눠야 b1:2와 b:12가 섞이지 않는다 } key = 조각.잇기(" "); 만약 (!groups.있나(key)) { groups[key] = []; } groups[key].넣기(name);}콘솔.쓰기(groups.개수);각각 (key 에서 groups.열쇠목록){ 콘솔.쓰기(key + " = " + groups[key].잇기(" "));}