백준 6064번: 카잉 달력 - javascript

2 분 소요

백준 6064번: 카잉 달력

문제 설명

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. 의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 M, N, x와 y가 주어질 때, 이 카잉 달력의 마지막 해라고 하면 는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 은 카잉 달력의 마지막 해를 나타낸다.

출력

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 가 k번째 해를 나타내는 것을 의미한다. 만일 에 의해 표현되는 해가 없다면, 즉, 가 유효하지 않은 표현이면, -1을 출력한다.

접근

문제 자체는 최소 공배수를 이용한 문제 같다. 수식으로 풀어보면 0부터 M과N의 최소공배수까지 늘어나는 i와 j가 있을 때,
한쪽은 Mxi+X, 다른 한쪽은 Nxj+Y 라 하고, 두 수가 같을 때의 값을 출력한다.
단, i와j는 M과N의 최소공배수를 넘지 않아야 하고 값이 없을경우 -1을 출력한다.
…
로 해석할 수 있다.
처음에는 최소공배수를 구하는데 있어서 유클리드 호제법을 사용하지 않고 brute force니깐 하면서 원초적으로 2부터 나눠서 올라가는 방법을 썼더니 시간 초과가 났다.
그래서 유클리드 호제법으로 바꿔서 최소공배수를 구해줬는데…
또 초과가 났다!

자세히 보니깐 내 코드에서 위에서 말한 각각의 i와 j의 최대 범위를 M과 N의 최소 공배수로 잡아놨던것이다.
이게 왜 문제였냐 하면, 내 경우에 어차피 x와y는 서로 다른 값이다.
따라서 1씩 올라갈 필요없이 서로 대소를 비교해 가면서 각각 M과 N씩 상승 시켜주는 방법을 썼기 때문이다…
그래서 각각 최소공배수에서 자신값인 M과 N을 나눈 범위까지 반복문을 돌려줬어야했는데 최소공배수로 돌려서 몇 배 또는 몇 만배까지 반복문이 돌아갔으니 당연히 시간초과가 날 수 밖에… ^^;

정리하자면

M과 N의 최소공배수가 멸망연도다.(최대 범위값)
X의 경우는 X에 계속 M을 더해준다.
Y의 경우는 Y에 계속 N을 더해준다.
X와 Y의 크기를 비교하면서 작은 쪽만 더하기를 한번씩 해준다.
이렇게 나온 X와Y가 서로 같을 때 출력해준다.
만약 멸망연도까지 같은 경우가 없었다면 -1을 출력한다.

이렇게 코드를 돌리면 충분히 시간안에 성공할 수 있다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성
  let answer ='';
  answer = ingka(input);
  console.log(answer)
  process.exit();
});

let ingka = function(input){  
  let answer = [];
  input.reduce((acc,cur)=>{
    let tmp = check_ingka(cur);
    answer.push(tmp);
  },'');
  return answer.join('\n')
}

let check_ingka = function(data){
  let input = data.split(' ');  
  let M = input[0]*1, N = input[1]*1, X = input[2]*1, Y = input[3]*1;  
  let x_cnt =0, y_cnt=0;  
  let answer = -1;
  let gcd = 0;
  if(M>N)gcd = gdc(M,N);
  gcd = gdc(N,M);
  while(x_cnt<=N/gcd && y_cnt<=M/gcd){    
    if(X==Y){
      answer = X;
      break;
    }else if(X>Y){
      Y = Y + N;
      y_cnt++;
    }else{
      X = X + M;
      x_cnt++;
    }    
  }
  return answer;
}

function gdc(a,b){
  return b ? gdc(b, a%b) : a;
}

Twitter Facebook LinkedIn

ryeon

백준 6064번: 카잉 달력 - javascript