문제
레시피의 각 재료가
w n/d형태의 대분수로 주어질 때, 정수 배율C를 곱한 결과를 다시 기약 대분수 형태로 출력한다.
풀이
대분수 w n/d를 가분수 (w*d + n) / d로 바꾸고 배율 C를 곱한다. 분자·분모를 GCD로 약분한 뒤 몫과 나머지로 다시 대분수 형태를 복원한다. 나머지가 0이면 정수만, 정수부가 0이면 0 n/d 형태로 출력한다.
코드
#include <iostream>
#include <cstdio>
using namespace std;
long long get_gcd(long long a, long long b) {
while (b) {
a %= b;
swap(a, b);
}
return a;
}
void solve(int idx) {
int I;
long long C;
if (!(cin >> I >> C)) return;
cout << "Data Set " << idx << ":" << endl;
for (int i = 0; i < I; ++i) {
long long w, n, d;
scanf("%lld %lld/%lld", &w, &n, &d);
long long total_n = (w * d + n) * C;
long long total_d = d;
long long common = get_gcd(total_n, total_d);
total_n /= common;
total_d /= common;
long long new_w = total_n / total_d;
long long new_n = total_n % total_d;
if (new_n == 0) {
cout << new_w << endl;
} else {
if (new_w == 0) cout << "0 " << new_n << "/" << total_d << endl;
else cout << new_w << " " << new_n << "/" << total_d << endl;
}
}
cout << endl;
}
int main() {
int K;
if (!(cin >> K)) return 0;
for (int i = 1; i <= K; ++i) {
solve(i);
}
return 0;
}복잡도
- 시간: O(I * log(max)) (I: 재료 수, GCD 계산 포함)
- 공간: O(1)