[백준 6064 - Node.js] 카잉 달력

🔗 문제 링크

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

6064번: 카잉 달력

✏️ 풀이

const [T, ...input] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');
const data = input.map(v => v.split(' ').map(Number));

const getGCD = (a, b) => {
  let x = Math.max(a, b);
  let y = Math.min(a, b);
  let remainder;
  while (y) {
    remainder = x % y;
    x = y;
    y = remainder;
  }
  return x;
};

const output = data.map(([M, N, x, y]) => {
  const lcm = M * N / getGCD(M, N);
  let year;
  for (let i = x; i <= lcm; i += M) {
    if ((i - 1) % N + 1 === y) {
      year = i;
      break;
    }
  }
  return year ? year : -1;
});

console.log(output.join('\n'));

문제 예시로 나온 M = 10, N = 12인 경우는 육십갑자(六十甲子)와 완전히 동일한 것으로 보아도 된다. x는 갑을병정무기경신임계 10개, y는 자축인묘진사오미신유술해 12개가 서로 번갈아가며 60을 주기로 반복된다(갑자, 을축, 병인, ... , 계해). 카잉 달력도 마찬가지로 생각하면 된다.

 

현재 카잉 달력의 x값은 실제 해가 M의 배수(0 포함) + x 중 하나라는 뜻이다. 그렇다면 M의 배수 + x인 해 중에서 y가 현재 y값으로 나오는 해를 찾으면 된다. 그러려면 x에 M을 계속 더해가면서 그 값을 N으로 나누었을 때 나머지가 y가 되는 값을 찾으면 된다. 이 때, y = N이라면 N의 나머지와 비교했을 때 0 != N이 되어 값을 찾지 못하게 된다. 따라서, (M의 배수 + x)를 N으로 나눈 나머지에 1을 더한 값이 현재 y값과 같을 때의 (M의 배수 + x)를 찾아야 한다.

 

주어진 값들 중에는 유효하지 않은 카잉 달력도 존재한다. 따라서, M의 배수 + x를 가능한 최댓값인 M과 N의 최소공배수까지만 확인해보고 해를 찾을 수 없을 때 -1을 출력하도록 해야 한다. 최소공배수는 두 수의 최대공약수를 구하고 두 수의 곱을 최대공약수로 나누어서 구할 수 있다.