[백준] 2609번 최대공약수와 최소공배수 (C++) - Euclidean algorithm

문제

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

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

코드

way1

#include <iostream>

using namespace std;

int main(){
  int a, b, d = 2;
  int lcm, gcd = 1;
  cin >> a >> b;

  while(!(d > a || d > b)){
    if(a%d==0 && b%d==0){
      a /= d;
      b /= d;
      gcd *= d;
    } else{
      d += 1;
    }
  }
  lcm = gcd*a*b;

  cout << gcd << '\n';
  cout << lcm << '\n';

  return 0;
}

 

way2

#include <iostream>

using namespace std;

int gcd(int a, int b){
  int c;
  while(b!=0){
    c = a%b;
    a = b;
    b = c;
  }
  return a;
}

int main(){
  int m, n;
  cin >> m >> n;

  int g = gcd(m,n);
  int lcm = m*n/g;

  cout << g << '\n';
  cout << lcm << '\n';

  return 0;
}

정리

way1

way1은 초중학교에서 배웠던 최대공약수 구하는 방법을 이용해 문제를 해결했다. a와 b 두 수 모두가 나누어 떨어질 경우 d(처음 값은 2)로 나누고 나누어 떨어지지 않을 경우 d에 1씩 더한다. 이를 a, b가 최대한 나누어떨어질동안 반복해서 해결했다.

 

 

way2

way2는 유클리드 호제법으로 문제를 해결했다.

 

예를들어 12와 18의 최대공약수를 유클리드 호제법을 이용한 way2방법으로 풀어보자.

a=12 b=18 → c=12%18=12, a=18, b=12

a=18 b=12 → c=18%12=6, a=12, b=6

a=12 b=6 → c=12%6=0, a=6, b=0

a=6 b=0 → b=0이므로 return 6

여기서 새롭게 하나 알 수 있는 것은 유클리드호제법에 대한 설명을 보면 a>b라는 조건이 붙어있는데 way2에서 사용한 알고리즘에서는 이를 고려하지 않아도 된다. 그 이유는 위 예시에서도 알 수 있듯이 while문을 한번 돌면서 a>b인 상태로 만들어주기 때문이다.

참조

https://terms.naver.com/entry.naver?docId=3552258&cid=58663&categoryId=58666

https://luv-n-interest.tistory.com/955

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95