백준 14490 : 백대열

• 문제 선정 이유 : 알고리즘 문제 해결 재활 용 낮은 난이도 문제 풀이
• Solved.ac 기준 실버 5
• 사용언어 C++

문제 해석

• 유클리드 호재법을 통한 최대 공약수 찾기

문제 풀이

1. ':'을 기점으로 n, m을 나눠야 하지만 한줄로 입력 받으므로 string 형태로 입력 받을 것
2. n, m을 int 형태로 변환해주고 최대공약수를 찾을 것

유클리트 호재법

• 임의의 숫자 n, m의 최대 공약수를 찾는 방법
• n, m을 제외한 모든 변수는 임의의 변수
• n >= m일 때를 가정

1. n = m * a + b
2. m = b * c + d
3. b = d * e + f
   ... 나머지가 0이 될 때 직전의 나머지(나머지가 0이 될 때의 약수 값이 최대 공약수)

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

int gcd(int a, int b) {									// 최대 공약수 구하는 함수
	if (a % b == 0) return b;							// 나누어 떨어지면 나누는 수를 반환
	else return gcd(b, a % b);							// 나누어 떨어지지 않으면 나누는 수를 나눌 수로 바꾸고 나머지를 나누는 수로 바꿔 재귀
}

string str;												// 입력
int n, m;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	
	cin >> str;
	

	for (int i = 0; i < str.size(); i++) {
		if (str[i] == ':') {							// ':' 전후로
			n = stoi(str.substr(0, i));					// 앞은 n
			m = stoi(str.substr(i + 1, str.size()));	// 뒤는 m

			break;										// 나눴으면 더 이상 반복할 필요 없으니 break
		}
	}

	int tmp = gcd(n, m);								// 함수 실행
	cout << n / tmp << ':' << m / tmp;					// 출력

	return 0;
}