백준] 3036 - 링(COCI 2006/2007)

시간 제한 : 1초

메모리 제한 : 128MB

입력

첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100)

다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다.

출력

출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.

소스코드

#include <iostream>
using namespace std;
int gcd(int a, int b)
{
	if (b == 0)
		return a;
	else
		return gcd(b, a%b);
}
int main(void)
{
	int n, left, g;
	int arr[100];
	cin >> n >> left;
	for (int i = 0; i < n - 1; i++)
		cin >> arr[i];
	for (int i = 0; i < n - 1; i++)
	{
		if (arr[i] > left)
			g = gcd(arr[i], left);
		else
			g = gcd(left, arr[i]);
		cout << left / g << "/" << arr[i] / g << '\n';
	}
}

Tip

유클리드 호제법으로 첫번째 기어와 다른 기어들의 최대공약수를 구해서 문제를 풀어나가면 된다.