링

문제

• 백준 3036번 - 링

언어

• JavaScript

순서도

1. 각각의 링을 첫 번째 링과 비교하며 몇 바퀴를 회전할지 구하기

문제 풀이 step 1

• 첫 번째 링을 한 바퀴 돌렸을 때, 각각의 링이 몇 바퀴 도는지 기약 분수 형태로 출력하는 문제입니다.
• 원의 둘레는 구하지 않고, 반지름과 나누기 연산을 통해서 몇 바퀴 도는지 계산합니다.
  • 원의 둘레를 구하지 않는 이유는 원의 둘레를 구할 때 곱했던 값들이 나누기 연산을 통해서 똑같이 나눠지기 때문입니다.
  • 예를 들어, 첫 번재 링의 반지름이 8 이고 두 번째 링의 반지름이 4 라면
    • 두 번째 링의 회전 횟수는 8 / 4 로 기약 분수 형태인 2 / 1 이 됩니다.

문제 풀이 step 2

• 간단하게 반지름을 나눔으로써 회전 횟수를 구할 수 있지만, 기약 분수 형태로 출력하는 부분 때문에 추가 연산이 필요합니다.
  • 그 추가 연산은 분자와 분모 사이의 최대공약수를 구하고, 각각 나누기 연산을 통해서 기약 분수 형태로 변환해주면 됩니다.
  • 최대공약수를 구하는 방법은 유클리드 호제법을 이용할 수 있고, 그에 관해서는 백준 2609번 - 최대공약수와 최소공배수 풀이 에 포스트되어 있습니다.
• 따라서, 각각의 링을 첫 번재 링과 비교하며 나누기 연산을 하고, 각 분자와 분모를 최대공약수로 나눠서 기약분수 형태로 출력하면 정답이 됩니다.
• 추가 설명은 주석에 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// 최대공약수를 구하는 함수
// 유클리드 호제법 : a % b = r 일 때, GCD (a, b) = GCD (b, r) 과 같고, r = 0 일 때, b 가 최대공약수
const GCD = (a, b) => {
	if (a % b === 0) return b;
	return GCD(b, a % b);
};

const solution = (input) => {
	const n = Number(input[0]);
	const arr = input[1].split(" ").map(Number);

	let res = "";
	const firstRun = arr[0];
	for (let i = 1; i < n; i++) {
		const gcd = GCD(firstRun, arr[i]);
		// 첫 번째 링의 반지름을 각각의 링의 반지름으로 나눠주고, 분자와 분모를 최대공약수로 나눠주기
		res += `${firstRun / gcd}/${arr[i] / gcd}\n`;
	}

	return res;
};

console.log(solution(input));