백준 링크 : https://www.acmicpc.net/problem/2609

문제 개요

입력값으로 두 개의 자연수가 주어지면, 두 자연수의 최대공약수와 최소공배수를 출력하는 문제이다.

아이디어

• 유클리드 호제법을 통해 최대공약수를 구한다.

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

• 최대공약수를 이용한 공식을 통해 최소공배수를 구한다.

  $$ \mathrm{lcm}(a, b) = \frac{|ab|}{\gcd(a, b)} $$

코드

// 아래의 코드는 dev c++환경에서 동작됩니다.
// visual studio에서는 bit/stdc++.h가 기본적으로 없기 때문에
// 정삭적인 작동이 되지 않을 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

#define lcm asdijfe
#define gcd kjfiejij
int input1, input2, a, b, temp, ret;
int gcd, lcm;

int GCD(int a, int b)
{
    int r
    while(r == 0) {
      r = a % b;
      a = b;
      b = r;
    }
    return a;
}

int main()
{
    ios::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
	
	cin >> input1 >> input2;
	
	a = max(input1, input2);
	b = min(input1, input2);
	
	gcd = GCD(a, b);
	
	cout << gcd << "\\n";
	
	lcm = abs(a * b) / gcd;
	cout << lcm;
    return 0;
}

후기

처음에는 단순 구현으로 해보려다가 결국 잘 안되서 실패가 떴다. 나무위키에 최대공약수에 대해 공부하고, 유클리드 호제법을 학습해서 문제를 다시 풀어봤다. 추가적으로 최소공배수는 공식을 그대로 구현하면 되서, 직접 코드로 작성했다.

그렇게 모르는 지식을 보충하고 다시 풀어보니 금방 해결됐다. 역시 문제 해결이 잘 안될때는 배경지식이 부족해서 안되는 경우도 많은 것 같다.