[BOJ] 2609번 : 최대공약수와 최소공배수

백준 2609번 : 최대공약수와 최소공배수

🔗 문제 링크

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

2609번: 최대공약수와 최소공배수

 

---

💬 문제

 최대공약수 와  최소공배수 에 대한 이해가 있다면, 충분히 풀 수 있는 문제다.

 

1. 첫 번째 줄에 공백을 기준으로 두 개의 자연수(a, b)가 주어진다.
   
   
2. 두 수의 최대 공약수와 최소 공배수를 구해 출력해준다.
   
   - a의 약수면서 b의 약수인 수 중에서 가장 큰 수가  최대공약수 다
   - a의 배수면서 b의 배수인 수 중에서 가장 작은 수가  최소공배수 다
   
   

 

---

💡 입력값 받아오기

JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.

이 문제에서는 1번째 줄에 자연수 a와 b가 주어진다. 공백을 기준으로 두 수를 잘라주고 정수화해준다.

 

 

입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.

https://valueengine.tistory.com/2

[BOJ] Node.js로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅

 

728x90

 

---

💻 풀이

이 문제는 총 2가지 방식으로 풀 수 있다.

🔑 풀이1 : for문으로 구하기

• 두 자연수가 주어졌을 때, a < b 순으로 정렬해주고 시작한다.
  
  
• 2부터 a까지의 수로 a와 b를 나눠 최대 공약수를 찾아준다.
  
  - 1은 모든 수의 공약수이므로, 변수 divisor에 1을 할당해주고 2부터 나눠준다
  
  
• 최소 공배수
  
  1) a가 최대 공약수라면 b는 a의 배수다
  2) 그렇지 않다면, a와 b를 최대 공약수로 나눠 최소 공배수를 구해준다
  
  

// input값 처리
const input = require('fs').readFileSync('/dev/stdin')
  .toString().trim().split(' ').map(Number);
[a, b] = input.sort((a, b) => a - b);  // a < b

console.log(solution(a, b));

function solution(a, b) {
  let divisor = 1;  // 약수
  let multiple;     // 배수

  // 최대 공약수
  for (let i=2; i <= a; i++) {
    if (a % i === 0 && b % i === 0) {
      divisor = i;
    }
  }
  // 최소 공배수
  if (a === divisor) {  // a가 최대 공약수라면
    multiple = (b / divisor) * divisor;
  } else {
    multiple = a * b / divisor;
  }
  return `${divisor}\n${multiple}`;
}

 

시간은 다음과 같이 걸렸다.

 

 

---

🔑 풀이2 : 유클리드 호제법

두 번째 방법은 최대공약수를 구하는 알고리즘인 유클리드 호제법을 이용하는 것이다.

더 자세한 내용은 아래 링크를 참고하길 바란다.

 

https://valueengine.tistory.com/30

[알고리즘] 유클리드 호제법

 

• a를 b로 나눠야 하니 a > b 순으로 정렬해주고 시작한다.
  
  
• x를 y로 나눠주고, 나머지가 0이 될 때까지 while문을 돌려준다.
  
  - 재할당해주면서 값이 바뀌므로 x, y로 해준다
  
  
• 만약 나머지가 0이 아니라면, x를 y로 바꿔주고, y는 새로운 나머지로 바꿔준다
  
  - 나머지가 0이 되면 그때의 y가 최대공약수다
  - 최소 공배수는 두 수의 곱을 최대공약수 y로 나눈 값이다
  
  

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);
[a, b] = input.sort((a, b) => b - a);  // a > b

console.log(solution(a, b));

function solution(x, y) {
  while (x % y !== 0) {
    let rest = x % y  // 나머지
    
    if (rest !== 0) {  // 나머지가 0일때 그 나머지 출력
      x = y;           // 나머지를 나눈수에 재할당
      y = rest;        // 나머지에 새 나머지 할당 
    }
  }
  return `${y}\n${(a * b / y)}`;
}

 

시간은 다음과 같이 걸렸다.