[C++] 백준 3036번 : 링

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

3036번: 링

---

 문제 풀이

기약 분수 형태로 출력하는 것만 신경 쓰면 되는 문제이다.

기약 분수로 만들기 위해서는 최대공약수로 나눠주면 된다!

결국 최대공약수를 구하는 문제이다!

 

 함수 Solution

첫 번째 원이 기준이니 2번째 원부터 따진다.

만약에 최대공약수가 없다면 있는 그대로 출력한다.

 느낀 점

유클리드 알고리즘만 알고 있다면 쉽게 해결할 문제이다!

 코드

#include <iostream>

using namespace std;

int n;
int radius[101];

int GCD(int a, int b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

void solution() {
	for (int i = 1; i < n; i++) {
		int gcd = GCD(radius[0], radius[i]);
		if (gcd == 1) 
			cout << radius[0] << "/" << radius[i] << "\n";
		else
			cout << radius[0] / gcd << "/" << radius[i] / gcd << "\n";
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n;i++) 
		cin >> radius[i];
	solution();
}