#3036 링

# 문제

# 입력 및 출력

# 풀이

기약 분수 형태로 출력해야 하기 때문에 최대공약수를 구해야 한다

최대 공약수를 구하기 위해 유클리드 호제법을 사용했음

https://kangworld.tistory.com/184

[코딩 팁] 최대공약수 : 유클리드 호제법 원리

위 블로그 참고

 

#include <iostream>
using namespace std;

int gcd(int first, int r) {
	int b, s, mod;
	if (first < r) b = r, s = first;
	else b = first, s = r;
	while (1) {
		mod = b % s;
		if (!mod) break;
		b = s;
		s = mod;
	}
	return s;
}

int main() {
	int n, first, r;
	cin >> n >> first;
	for (int i = 0; i < n - 1; i++) {
		cin >> r;
		int mod = gcd(first, r);
		cout << first / mod << "/" << r / mod << "\n";
	}
}

처음에 제출했을 땐 큰 수도 작은수로 변경을 해줘야하는지 모르고 작은 수만 나머지로 변경을 해준 상태였다

그래서 두번 틀렸다ㅋㅋ

 

유클리드 호제법은 처음 들어보는데 매우 간단한 알고리즘으로 유용하게 쓰일 것 같다