[알고리즘/문제풀이/BOJ 3036번] 링

링 문제는 원주의 비율과 최대공약수를 활용하는 문제입니다. 원주가 반지름에 비례한다는 사실을 이용하여 회전수를 구하고 최대공약수를 이용하여 기약분수 형태로 출력함으로써 문제를 해결할 수 있습니다.

작성한 코드는 다음과 같습니다.

---

#include<stdio.h>
//기약분수는 최대공약수로 생성
int N;
int temp, temp1, temp2;

int gcd(int a, int b) {
	int temp;
	if (a < b) {
		temp = b;
		b = a;
		a = temp;
	}

	while (a % b != 0) {
		temp = b;
		b = a % b;
		a = temp;
	}

	return b;
}

int main(void) {
	scanf("%d", &N);
	scanf("%d", &temp1);

	for (int i = 0; i < N-1; i++) {
		scanf("%d", &temp2);
		temp = gcd(temp1, temp2);
		printf("%d/%d\n", temp1 / temp, temp2 / temp);
	}
}

문제의 지문은 다음의 링크에서 확인할 수 있습니다.

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