백준 3036번 C++

백준 3036번 링

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

3036번: 링

정답 코드

#include<iostream>
using namespace std;
int arr[100];
int find(int a, int b);
int main() {
	int n;
	cin >> n;
	for (int x = 0; x < n; x++)
		cin >> arr[x];
	for (int x = 0; x < n - 1; x++) {
		int res = find(arr[0], arr[x + 1]);
		cout << arr[0] / res << "/" << arr[x + 1] / res << "\n";
	}
}
int find(int a, int b) {
	if (a < b)
		swap(a, b);
	int res = 0;
	while (b != 0) {
		res = a % b;
		a = b;
		b = res;
	}
	return a;
}

문제 풀이

첫 번째 원을 기준으로 각각의 원에 대한 최대공약수를
구해서 나누어서 풀었습니다. 공약수 알고리즘은 유클리드 호제법을 이용하였습니다.