[BOJ16430][C++] 제리와 톰

문제

톰은 마트에서 치즈 1kg 을 사서 집으로 돌아왔습니다.

그런데 톰이 한눈을 판 사이 제리가 와서 A/B kg 만큼 훔쳐갔습니다.

제리가 치즈를 훔쳐 간 후 톰이 가지고 있는 치즈의 무게는 얼마인가요?

 

입력

첫 번째 줄에 두 정수 A, B (1 ≤ A < B ≤ 9) 가 주어집니다. 

A와 B는 서로소임이 보장됩니다.

 

 

출력

정답을 기약분수로 표현했을 때 P/Q kg 이라면 첫 번째 줄에 P와 Q를 공백을 사이에 두고 출력합니다. 

 

 

예제 입력 1

2 7

 

예제 출력 1

5 7

 

예제 입력 2

5 8

 

예제 출력 2

3 8

 

 

출처

University > 경북대학교 > 2018 Goricon 🐭번

· 문제를 만든 사람: exqt

 

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

#include <iostream> using namespace std;   int gcd(int p, int q);   int main() {     int A, B, P, Q, num;          cin >> A >> B;          P = B - A;     Q = B;          num = gcd(P, Q);     P = P / num;     Q = Q / num;          cout << P << " " << Q << endl;          return 0; }   int gcd(int m, int n)  {     if (m == 0) return n;     else return gcd(n % m, m); }

---

최소공약수(GCD)를 구하는 알고리즘을 이용하여 푼 문제였다.

기약 분수와 관련된 문제는 유클리드 호제법과 깊은 연관이 있기에 GCD 알고리즘을 이용하여 이 문제를 풀었다.

우선 입력 받은 분모의 값(B)을 분자의 값(A)과 뺀 값을 변수 P에 대입하였다.

그리고 분모의 값(B)를 Q에 대입하였다.

여기서 P/Q 값이 기약분수일 경우 (예: 5/7, 3/8) P와 Q가 각각 출력이 되도록 하면 되지만,

P/Q 값이 기약분수가 아닐 경우 (예: 4/8, 3/6) 위의 방법대로 하면 문제가 생긴다. 

문제의 조건대로 기약분수 형태로 표현해서 생긴 값을 출력해야 하므로, GCD 알고리즘을 이용하여 P와 Q를 P와 Q의 최대공약수(num)로 나눈 값을 각각 P, Q에 대입하여 출력한다.