Computer Science/Algorithm Problem

백준] 14490 - 백대열(선린인터넷고등학교 교내대회)

TwinParadox 2018. 10. 17. 22:00
728x90

시간 제한 : 2초

메모리 제한 : 512MB




입력

n과 m이 :을 사이에 두고 주어진다. (1 <= n, m <= 100,000,000)




출력

두 수를 최대한으로 약분하여 출력한다.




소스코드

#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(void)
{
	string str;
	int pos, g, a, b, len;
	cin >> str;
	len = str.length();
	pos = str.find(':');
	a = stoi(str.substr(0, pos));
	b = stoi(str.substr(pos + 1, len - pos));

	if (a > b)
		g = gcd(a, b);
	else
		g = gcd(b, a);

	cout << a / g << ":" << b / g;
}




Tip

string 헤더 파일에 있는 함수들을 잘 사용하면, 유클리드 호제법만 해결하면 되는 거라 쉽게 풀 수 있는 문제긴 하나, 문제 푸는 환경에 따라 그것들을 사용하지 못한 경우가 있다. 그렇게 되면 문자열 처리가 더 중요해지는 문제..



728x90