[Baekjoon]3036번 링 - Javascript

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

3036번: 링

문제

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

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

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

입력

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

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

출력

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

예제 입력 1 복사

3
8 4 2

예제 출력 1 복사

2/1
4/1

 

문제풀이(1)

문제의 풀이가 생각나지 않아서 찾아본 결과 최대공약수를 이용한 문제라는 것을 알게되었다.
2수의 최대공약수를 찾아서 기약분수(?)의 형태로 출력한면 된다고 한다.
첫번째 링이 돌아가면 나머지 링도 돌기 때문에 첫번째 링과 나머지 링의 최대공약수를 찾아 기약분수의 형태로 나타내면 된다.
최대공약수는 유클리드 호제법을 사용해서 구하는 방식을 사용하려고 한다.
8과 4의 최대 공약수 = 4 -> (8/4)/(4/4) -> 2/1
8과 2의 최대 공약수 = 2 -> (8/2)/(2/2) -> 4/1

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
const arr = input[0].split(" ").map(Number);
const firstNum = arr[0];

// 유클리드 호제법 최대공약수 구하기
const gcd = (a, b) => {
  if (a % b === 0) {
    return b;
  }
  return gcd(b, a % b);
};

for (let i = 1; i < N; i++) {
  const nowNum = arr[i];
  const resultGCD = gcd(firstNum, nowNum);
  console.log(`${firstNum / resultGCD}/${nowNum / resultGCD}`);
}