[BOJ] 14490번 백대열 (C++)

https://www.acmicpc.net/problem/14490

14490번: 백대열

 

#include <iostream>
#include <string>
using namespace std;

int gcd(int a, int b){
	if(b == 0) return a;
	else return gcd(b, a % b);
}

int main() {
	string s;
	cin >> s;
	
	int idx = s.find(":");
	int n = stoi(s.substr(0, idx));
	int m = stoi(s.substr(idx + 1, -1));
	int gcf = gcd(n, m);
	
	cout << n / gcf << ":" << m / gcf;
	return 0;
}

유클리드 호제법으로 n과 m의 최대공약수를 구하고 n과 m을 각각 최대공약수로 나누어 약분한다.