분수 n개가 한 줄에 하나씩 p/q 꼴로 주어진다(분자 p는 음수일 수 있고, 분모 q는 양수이다.
입력의 분수는 기약분수가 아닐 수도 있다).
이 분수들을 모두 더한 값을 기약분수로 출력하라.
기약분수란 분자와 분모의 최대공약수가 1이고 분모가 양수인 꼴이며, 음수이면 부호는 분자에 붙인다(예: -1/12).
합이 정수이면(0 포함) /와 분모 없이 정수만 출력한다.
첫 줄에 n, 그다음 n줄에 분수가 하나씩 빈칸 없이 주어진다.
a/b(b ≥ 2) 또는 정수 하나3 1/2 1/3 1/6
1
2 -1/4 1/6
-1/12
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
지금까지의 합 num/den에 p/q를 더할 때 두 분모의 최소공배수 L = den / gcd(den, q) * q로 통분해 num = num * (L / den) + p * (L / q), den = L로 두고, 그때마다 gcd(num, den)으로 나눠 약분해요.
분모를 그냥 곱해 가면 30¹⁰ ≈ 6×10¹⁴까지 커지고 분자는 그보다 더 커져서, JavaScript·TypeScript·크레이콘의 수(2^53까지 정확)에서는 정확하지 않게 돼요.
통분해도 분모는 최대 lcm(1…30) ≈ 2.3×10¹²이라 C·C++·Java·C#은 int가 아니라 long/long long이 필요해요.
가장 큰 함정은 음수의 나머지예요: C·C++·Java·C#·JavaScript·TypeScript·크레이콘의 %는 앞 수의 부호를 따라서(-3 % 6은 -3) 손으로 짠 유클리드 호제법이 음수 gcd를 돌려줄 수 있고, 그걸로 나누면 분모가 음수가 돼요(1/-12).
그래서 gcd 안에서 먼저 절댓값을 써요.
Python의 %는 뒤 수의 부호를 따르고, math.gcd와 C++17 std::gcd·std::lcm(<numeric>)은 늘 0 이상을 돌려줘서 이 걱정이 없어요.
Java·C#·C·JavaScript에는 정수 gcd가 기본으로 없어서(Java는 BigInteger.gcd뿐) 직접 짜요.
크레이콘은 최대공약수(a, b) 함수를 만들고 수학.절댓값, 수학.몫을 써요(/는 소수 나눗셈이에요).
입력 p/q는 Python split("/"), C scanf("%lld/%lld"), C++ cin >> p >> slash >> q, 크레이콘 나누기("/")로 나눠요.
마지막으로 정수가 된 합은 3/1이나 0/1이 아니라 3, 0으로 써요.
from math import gcd n = int(input())num, den = 0, 1 # 지금까지의 합 num/den (늘 기약분수, den > 0)for _ in range(n): p, q = map(int, input().split("/")) lcm = den // gcd(den, q) * q # 두 분모의 최소공배수로 통분 num = num * (lcm // den) + p * (lcm // q) den = lcm g = gcd(num, den) # math.gcd는 음수를 받아도 0 이상을 돌려준다 num //= g den //= gprint(num if den == 1 else f"{num}/{den}")const lines = require("fs").readFileSync(0, "utf8").trim().split(/\r?\n/); // %는 앞 수의 부호를 따라서 음수가 들어오면 음수 gcd가 나올 수 있다 → 절댓값으로 계산const gcd = (a, b) => { a = Math.abs(a); b = Math.abs(b); while (b !== 0) [a, b] = [b, a % b]; return a;}; const n = Number(lines[0]);let num = 0, den = 1; // 지금까지의 합 num/den (늘 기약분수, den > 0)for (let i = 1; i <= n; i++) { const [p, q] = lines[i].trim().split("/").map(Number); const lcm = (den / gcd(den, q)) * q; // 두 분모의 최소공배수로 통분 num = num * (lcm / den) + p * (lcm / q); den = lcm; const g = gcd(num, den); num /= g; den /= g;}console.log(den === 1 ? `${num}` : `${num}/${den}`);import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").trim().split(/\r?\n/); // %는 앞 수의 부호를 따라서 음수가 들어오면 음수 gcd가 나올 수 있다 → 절댓값으로 계산function gcd(a: number, b: number): number { a = Math.abs(a); b = Math.abs(b); while (b !== 0) [a, b] = [b, a % b]; return a;} const n = Number(lines[0]);let num = 0, den = 1; // 지금까지의 합 num/den (늘 기약분수, den > 0)for (let i = 1; i <= n; i++) { const [p, q] = lines[i].trim().split("/").map(Number); const lcm = (den / gcd(den, q)) * q; // 두 분모의 최소공배수로 통분 num = num * (lcm / den) + p * (lcm / q); den = lcm; const g = gcd(num, den); num /= g; den /= g;}console.log(den === 1 ? `${num}` : `${num}/${den}`);import java.util.Scanner; public class Main { // %는 앞 수의 부호를 따라서 음수가 들어오면 음수 gcd가 나올 수 있다 → 절댓값으로 계산 static long gcd(long a, long b) { a = Math.abs(a); b = Math.abs(b); while (b != 0) { long t = a % b; a = b; b = t; } return a; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = Integer.parseInt(sc.nextLine().trim()); long num = 0, den = 1; // 지금까지의 합 num/den (늘 기약분수, den > 0) for (int i = 0; i < n; i++) { String[] pq = sc.nextLine().trim().split("/"); long p = Long.parseLong(pq[0]), q = Long.parseLong(pq[1]); long lcm = den / gcd(den, q) * q; // 두 분모의 최소공배수로 통분 num = num * (lcm / den) + p * (lcm / q); den = lcm; long g = gcd(num, den); num /= g; den /= g; } System.out.println(den == 1 ? String.valueOf(num) : num + "/" + den); }}using System; class Program{ // %는 앞 수의 부호를 따라서 음수가 들어오면 음수 gcd가 나올 수 있다 → 절댓값으로 계산 static long Gcd(long a, long b) { a = Math.Abs(a); b = Math.Abs(b); while (b != 0) (a, b) = (b, a % b); return a; } static void Main() { int n = int.Parse(Console.ReadLine()); long num = 0, den = 1; // 지금까지의 합 num/den (늘 기약분수, den > 0) for (int i = 0; i < n; i++) { string[] pq = Console.ReadLine().Trim().Split('/'); long p = long.Parse(pq[0]), q = long.Parse(pq[1]); long lcm = den / Gcd(den, q) * q; // 두 분모의 최소공배수로 통분 num = num * (lcm / den) + p * (lcm / q); den = lcm; long g = Gcd(num, den); num /= g; den /= g; } Console.WriteLine(den == 1 ? $"{num}" : $"{num}/{den}"); }}#include <iostream>#include <numeric> int main() { int n; std::cin >> n; long long num = 0, den = 1; // 지금까지의 합 num/den (늘 기약분수, den > 0) for (int i = 0; i < n; i++) { long long p, q; char slash; std::cin >> p >> slash >> q; long long lcm = std::lcm(den, q); // 두 분모의 최소공배수로 통분 num = num * (lcm / den) + p * (lcm / q); den = lcm; long long g = std::gcd(num, den); // std::gcd는 음수를 받아도 0 이상을 돌려준다 num /= g; den /= g; } if (den == 1) std::cout << num << '\n'; else std::cout << num << '/' << den << '\n';}#include <stdio.h>#include <stdlib.h> /* %는 앞 수의 부호를 따라서 음수가 들어오면 음수 gcd가 나올 수 있다 → 절댓값으로 계산 */static long long gcd(long long a, long long b) { a = llabs(a); b = llabs(b); while (b != 0) { long long t = a % b; a = b; b = t; } return a;} int main(void) { int n; scanf("%d", &n); long long num = 0, den = 1; /* 지금까지의 합 num/den (늘 기약분수, den > 0) */ for (int i = 0; i < n; i++) { long long p, q; scanf("%lld/%lld", &p, &q); long long lcm = den / gcd(den, q) * q; /* 두 분모의 최소공배수로 통분 */ num = num * (lcm / den) + p * (lcm / q); den = lcm; long long g = gcd(num, den); num /= g; den /= g; } if (den == 1) printf("%lld\n", num); else printf("%lld/%lld\n", num, den); return 0;}// %는 앞 수의 부호를 따라서 음수가 들어오면 음수 gcd가 나올 수 있다 → 절댓값으로 계산최대공약수(a, b){ a = 수학.절댓값(a); b = 수학.절댓값(b); 동안 (b != 0) { t = a % b; a = b; b = t; } 돌려주기 a;} n = 콘솔.줄읽기().수로변환();num = 0;den = 1; // 지금까지의 합 num/den (늘 기약분수, den > 0)반복 (i = 0; i < n; i++){ pq = 콘솔.줄읽기().공백제거().나누기("/"); p = pq[0].수로변환(); q = pq[1].수로변환(); lcm = 수학.몫(den, 최대공약수(den, q)) * q; // 두 분모의 최소공배수로 통분 num = num * 수학.몫(lcm, den) + p * 수학.몫(lcm, q); den = lcm; g = 최대공약수(num, den); num = 수학.몫(num, g); den = 수학.몫(den, g);}만약 (den == 1){ 콘솔.쓰기(num);}아니면{ 콘솔.쓰기(num + "/" + den);}