프로그래머스 - 최대공약수와 최소공배수 - C++

 

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    
    int a = (n>m)? m : n;
    
    for(int i=a; i>=1;i--)
    {
        if(n%i==0 && m%i==0)
        {
            answer.push_back(i); break;
        }
    }
    int oM=m;
    int oN=n;
    int nCnt=2;
    int mCnt=2;
    while(true)
    {
        if(n==m)
        {
            answer.push_back(n);break;
        }
        if(n>m)
        {
            m=oM;
            m*=mCnt;
            mCnt++;
        }
        else
        {
            n=oN;
            n*=nCnt;
            nCnt++;
        }
    }
    return answer;
}

 

최대공약수와 최소공배수를 구하는 문제이다. 

널리 알려진 풀이방법이 있지만 혼자 힘으로 풀어보고자 했다. 

최대공약수는 공약수 중 가장 큰 수이기 때문에 단순하게 둘 중 더 작은 수부터 -1씩 해가며 

두 수를 모두 나누어 떨어지게 하는지 확인하였다. 

 

if(n%i==0 && m%i==0)
        {
            answer.push_back(i); break;
        }

만약 공약수이면 answer에 넣고 멈춘다. 

이 때의 공약수는 i를 큰수부터 -1씩해왔기 때문에 최대공약수가 된다. 

 

최소공배수는 둘이 같은지를 확인하고 다르면 더 작은 수에 기존 그 수만큼을 더하고 비교하는 방식으로 구했다.

예를 들어 n=3, m=5 이면

n = 3,6,9,12,15... , m = 5,10,15,20... 

if(n>m)
        {
            m=oM;
            m*=mCnt;
            mCnt++;
        }
        else
        {
            n=oN;
            n*=nCnt;
            nCnt++;
        }

m이 더 작으면 m에 숫자를 더하고 다시 n==m 인지 비교하는 방식으로 최소공배수를 구하였다.