[Baekjoon/백준] 3036번: 링(C/C++)

단계별로 풀어보기 17단계(정수론 및 조합론) 6번 문제

https://www.acmicpc.net/step/18

정수론 및 조합론 단계

---

백준 3036번: 링

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

3036번: 링

---

문제 설명

상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다.

상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다.

링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오.

---

입력과 출력

입력: 첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100) 다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다.

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

---

접근 방법

이번 문제는 링의 개수 N을 입력받고 바닥에 놓은 링의 반지름 N개를 입력받아서, 첫번째 링을 한바퀴 돌릴때 나머지 바퀴는 몇바퀴가 도는지 출력하는 문제다.

링이 돈다는 것에서 처음에는 조금 어렵게 느껴졌지만, 출력 설명에서 기약 분수(이미 약분이 다 끝난 분수)형태로 출력하라는 것을 보고 그냥 최대 공약수를 구해 나눠주면 되겠다는 것을 알게되었다. 그래서 첫번째 링 반지름을 기준점으로 잡아서 분자 값은 '첫번째 배열 / 최대 공약수', 분모 값은 'i번째 배열 / 최대 공약수'를 해주면 문제를 해결할 수 있다.

 

---

코드

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101

int rings[MAX];

int GCD(int A, int B) {
	int C = A % B;

	while (C != 0) {
		A = B;
		B = C;
		C = A % B;
	}

	return B;
}

int main(int argc, char * argv[]) {
	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> rings[i];

	for (int i = 1; i < N; i++)
		cout << rings[0] / GCD(rings[0], rings[i]) << "/" << rings[i] / GCD(rings[0], rings[i]) << endl;

	return 0;
}

---

결과

백준 제출 결과