🐢꾸준함의 미학

백준 6064 카잉 달력

8 min read

문제

분석하기

카잉 제국의 달력은 각 년도를 <x:y>와 같은 형식으로 표현한다 시초에 해당하는 첫번째 해를 <1:1>로 표현하고 두번째 해를 <2:2>로 표현한다.

<x:y>의 다음 해는 <x’:y’>로, x<M이면 x’ = x+1, x=M이면 x’=1이다. 이는 y도 N과 비교했을 때 똑같이 작용한다. M=10, N=12일 때

  • 첫번째 해
    • <1:1>
  • 11번째 해의 경우
    • <11:11>이지만 10번째 해로 넘어갈 때 x쪽의 값은 10까지 갔지만 열한번째 해로 넘어가면서 x는 M과 같은 상태이기 때문에 다시 1로 변했다. y의 경우는 N이 12이므로 11이 그대로 넘어가 <1:11> 이 되었다.
  • 13번째 해의 경우
    • <13:13>이지만 11번째 해로 넘어갈 때 이미 x는 1로 변했다. 그렇기 때문에 2가 더해져 3이 되고, y의 경우는 N이 12이기 때문에 13이 되는 순간 1이 되었다. 따라서 여기에서 알 수 있는 내용은 각 M, N에 따라서 x는 x%M, y는 y%N이 된다는 점이다. 이런 식으로 달력은 넘어간다.

우리가 풀어야 할 것은 각 줄마다 M, N, x, y가 주어지는데, 여기서 <x:y>를 보고 몇번째 해인지 맞춰야 한다.

하지만 여기서 고려해야 할 사항이 있다. 위 예제처럼 카잉 달력이 유효하지 않은 경우, -1을 출력하도록 하였다. 그러므로 선형으로 브루트포스하게 푸는 것은 되지 않는다. 그러므로 제대로 계산이 되지 않을 수도 있다는 것이다. 이 예외까지 고려할 수 있는 로직을 생각해보아야 한다.

가장 먼저 생각난 것은 재귀 방식으로 푸는 것이다. 어디서 시작했든 현재 가지고 있는 카잉 달력에서 계속 계산을 해나가다보면 유효한 달력일 경우 언젠가 1 1의 형태가 나올 것이다. 또한 유효하지 않은 카잉 달력일 경우, 계속 재귀적으로 달력을 구해 나가다가 x에서 가장 큰 수인 M이고, N이 가장 큰 수가 된다면 이건 영원히 끝나지 않을 것이라 생각할 수 있다.

다시금 x는 x%M, y는 y%N이 된다는 사실을 떠올리자. 그렇다면 한 년도에 각각 M,N으로 나누었을 때 나머지가 x,y처럼 나와야 한다는 뜻이기도 하다. 그럼 그 년도를 어떻게 찾을까? x,y의 나머지가 남는 년도에서 교집합을 찾으면 될 것 같다 첫번째 입력의 경우 10의 배수 + 3 해서 나오는 수들과 12의 배수 + 9 해서 나오는 수들 중에 교집합이 있는지 보면

  • x의 경우 → 3, 13, 23, 33, 43, 53..(3 + 10n)
  • y의 경우 → 9, 21, 33, 45, 57, 69…(9 + 12n) 이렇게 첫 수를 각각 x, y로 둔 M, N의 등차수열임을 알 수 있다. 그렇다면 이 두 공차의 최소공배수를 기준으로 이 달력이 반복된다는 것이기 때문에 해당 최대공배수 전까지 루프를 돌면서 x,y가 조건에 만족하는 해가 있는지 찾아보면 된다.

유클리드 호제법

유클리드 호제법은 x를 y로 나눈 나머지는 r일 때, x, y의 최대공약수는 y, r의 최대공약수와 같다는 원리이다. 이 원리를 사용해 x값에 y를 대입하고, y값에 r을 대입하면 r이 0이 될 때 둘의 최대공약수인 것이다. 그리고 최소공배수는 두 수의 곱에 최대공약수로 나누면 나온다.

function gcd(a, b) {
  if (a < b) {
    const temp = a;
    a = b;
    b = temp;
  }
  while (b != 0) {
    const temp = a % b;
    a = b;
    b = temp;
  }
}
 
function lcm(a, b) {
  (a * b) / gcd(a, b);
}

다시 돌아와서

10과 12의 최대공약수를 구해보면 2가 나온다. 최소공배수는 두 수의 곱 / 최대공약수 이므로10 * 12 / 2 = 60이다. 따라서 우리는 최소공배수인 60을 주기로 달력이 반복된다는 사실을 알 수 있고, 이전까지만 루프를 돌아서 공통되는 년도를 찾으면 된다.

function findYear(M, N, x, y) {
  const maxYear = lcm(M, N);
 
  let year = x;
  while (year <= maxYear) {
    if (year === 0) {
      if (y === x) return maxYear;
    } else if (year % N === y || (year % N === 0 && y === N)) {
      return year;
    }
    year += M;
  }
 
  return -1;
}

x를 기준으로 3, 13, 23, 33…이렇게 올라가지만서도 최소공배수인 120까지만 루프를 돌면서 y가 조건에 맞을 때가 있는지 확인한다. 조건에 맞는 경우는

  • x가 가지는 연도 중에 N으로 나눴을 때 y의 나머지가 나오는 경우
  • x가 가지는 연도 중에 N으로 나눴을 때 나머지가 없고 최대년도에 딱 맞춘 숫자일 때 이기 때문에 루프를 돌면서 검사하고, 만약 return문으로 빠져나가지 못했다면 서로 공통이 되는 숫자가 없다는 뜻이므로 -1을 출력한다.

전체 코드

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [t, ...rest] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
function gcd(a, b) {
  while (b !== 0) {
    const r = a % b;
    a = b;
    b = r;
  }
  return a;
}
 
function lcm(a, b) {
  return (a * b) / gcd(a, b);
}
 
function findYear(M, N, x, y) {
  const maxYear = lcm(M, N);
 
  let year = x;
  while (year <= maxYear) {
    if (year === 0) {
      if (y === x) return maxYear;
    } else if (year % N === y || (year % N === 0 && y === N)) {
      return year;
    }
    year += M;
  }
 
  return -1;
}
 
rest.forEach((input) => {
  const [M, N, x, y] = input.split(" ").map(Number);
  console.log(findYear(M, N, x, y));
});

그래프 뷰

백링크