백준3036 - 링 (유클리드 호제법) JS

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

문제는 다음과 같이 이어진 링이 있다고 할 때,

첫 번째 링을 돌릴 시 다음 링이 몇 바퀴 도는지 출력하는 문제다.

 

먼저 수학적인 접근을 해본다.

예제 1과 같은 예시로 8, 4, 2의 링이 있다고 할 때, 첫 번째 반지름 8인 링의 둘레는 16π 이다. (모든 링이 16π를 만족할 만큼 회전해야 한다는 의미기도 하다.)

이때 반지름 4인 링의 둘레는 8π 로  2바퀴(2/1)가, 반지름 2인 링의 경우 4π로 4바퀴(4/1)가 답이 된다.

(밑에서는 둘레를 구한 뒤 계산하지는 않는다.)

 

사실 해당 문제에서 가장 중요한 포인트는 '기약분수' 형태로 답안을 제출하는 것인데, 

우리는 중학교 때 배웠던 것처럼 최대공약수를 구한 뒤, 분자와 분모에 각각 최대공약수를 나눠 제출하면 된다.

 

이때 최대공약수(또는 최소공배수)를 구할 때는 '유클리드 호제법'이라는 알고리즘으로 해결하면 되는데,

유클리드 호제법이란 두 개의 정수를 나누어가며 최대공약수를 찾는 방식이라고 말할 수 있다.

 

유클리드 호제법을 코드로 표현하면 다음과 같다. 

 function euclidean(n,m) { // 유클리드 호제법
   // 무엇이 더 큰 수냐에 따라 변수 선언
  let a = n >= m ? n : m 
  let b = n < m ? n : m 
  
  // 작은 수인 변수 b가 0이 될 때까지 루프
  // b가 0이 되는 경우, a는 최대공약수가 됨
  while (b !== 0){ 
    let temp = a%b
    a = b
    b = temp
  }
  const gcd = a // 최대공약수 => 5
  // 최대공약수를 구하면 다음과 같이 최소공배수도 구할 수 있음
  const lcm = (n*m)/a // 최소공배수 => 15
}

euclidean(15,5)

 

다시 문제로 돌아와서 유클리드 호제법을 적용한 전체 문제 풀이는 다음과 같다.

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

// 유클리드 호제법
const act = (dif, n) => {
  let x = dif >= n ? dif : n
  let y = dif < n ? dif : n

  while (y !== 0) {
    let temp = x % y
    x = y
    y = temp
  }

  return `${dif/x}/${n/x}`
}

function solution(data) {
  const [_, arr] = data.map(el => el.split(' ').map(Number))
  // 기준이 될 첫번째 링은 편의상 빼서 선언
  const dif = arr.shift()
  const result = arr.map(el => act(dif, el))
  console.log(result.join('\n'))
}

solution(input)