⚫문제
🟡생각
최대한 약분하여 출력한다 -> 기약분수의 형태로 출력한다.(사실 분수형태는 아니라서 기약분수라고 할 수는 없지만 그냥 쉽게 생각해서 기약분수라고 표현했다.)
기약분수는, 분자와 분모의 최대공약수로 서로 나누어 더이상 나눌 수 없을때까지 약분한 분수이다.
그렇다면 최대공약수는 어떻게 구할까? GCD (Greatest Common Divisor)는 최대공약수라는 뜻이며, 두 자연수의 가장 큰 공통된 약수라고 뜻한다. GCD 알고리즘은 유클리드 호제법을 사용하는것으로 유명하다.
유클리드 호제법이란 간단하게 O(logN)의 시간복잡도로 두 자연수의 최대 공약수를 구할 수 있는 알고리즘이다.
기존의 방법(브루트 포스)도 O(N)의 시간복잡도로 나쁘지는 않지만 효율을 높히기 위해 이 알고리즘을 사용한다.
a를 b로 나눈 나머지를 r이라고 할때 (단, a > b) a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다는 성질을 이용한다.
이런 성질을 통해서 b와 r의 최대 공약수 r0를 구하고, 다시 r을 r0로 나눈 나머지를 구하는 과정을 반복하여(recursive) 나머지가 0이 되었을 때의 그 몫이 a와 b의 최대 공약수이다.
이를 수식으로 나타내면 아래와 같다.
GCD(A, B) = GCD(B, A%B)
if A%B = 0 -> GCD = B
else GCD(B, A%B)재귀로 반복하여 구한다.
나는 C++ STL의 numeric 컨테이너를 사용해서 gcd함수를 사용했다.
🟢 구현
#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
#define fastIo \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
string str;
string s1;
string s2;
bool flag = false;
int main() {
fastIo;
cin >> str;
for (int i = 0; i < str.length(); i++) {
if (str[i] == ':') {
flag = true;
}
if (!flag) {
s1 += str[i];
} else {
// 이 코드가 있어야 s2에 ':' 이게 안들어가 ㅇㅇ
if (str[i] != ':') {
s2 += str[i];
}
}
}
// cout << s1 << "\n";
// cout << s2 << "\n";
int ss1 = stoi(s1);
int ss2 = stoi(s2);
int ggcd = gcd(ss1, ss2);
cout << ss1 / ggcd << ":" << ss2 / ggcd;
return 0;
}중간에 콜론(':') 때문에 조금 애먹었지만 금방 해결했다~
근 성