[C++ 풀이] 2702번. 초6 수학

문제 분석

두 정수간의 최대공약수와 최소공배수를 찾는 문제이다.

구글링을 해본 결과 유클리드 호제법이 가장 유명하고 많이 쓰이길래 나도 그 방법으로 풀었다. 

또 최대공약수와 최소공배수간의 관계식을 참고했다.

• 최대공약수*최소공배수 = 두 수의 곱

 

알고리즘 설계

위에서 설명한대로, 유클리드 호제법과 두 관계식을 이용해서 풀었다. 

 

최대공약수와 최소공배수를 찾는 코드는 함수로 작성하여 각 케이스마다 함수를 적용하여 풀었다. 

 

코드

#include <iostream>
using namespace std;
/*
    1. 테스트개수t를 입력받는다.
    2. 정수 a와 b를 입력받는다.
    3. 각 최소공배수와 최대공약수를 출력한다.
*/

//최대공약수 gcd 
int gcd(int a, int b) {
    int c = a % b; 
    while (c != 0) {
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}
//최소공배수 lcm
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main() {
    //1
    int t;
    cin >> t;

    //2
    int a, b;
    while (t--) {
        cin >> a >> b;

        //최대공약수 gcd
        //최소공배수 lcm
        cout <<  lcm(a, b) << ' ' << gcd(a, b) <<  '\n';
    }

    return 0;
}

 

느낀 점

이렇게 공식화되어 있는 문제들은 내가 빨리 이 공식을 받아들이고 흡수하는 게 중요한 것 같다.