[프로그래머스] 프로그래머스 Level2 N개의 최소공배수 C++

문제

https://programmers.co.kr/learn/courses/30/lessons/12953

코딩테스트 연습 - N개의 최소공배수

풀이

유클리드 호제법을 통해 문제를 해결할 수 있었다.

일반적인 최소공배수 구하기 문제와 다르게 2개의 자연수만 비교하여 최소공배수를 리턴하는 것이 아닌 N개(N >= 2)가 모두 만족하는 최소공배수를 구해야하는 것이 조금 달랐다.

이는 최소공배수를 여러번 구해주면 되는데 예를들어 자연수 A, B, C가 있다고 가정할 때 A, B, C의 최소공배수는 A, B의 최소공배수를 구한 후 A, B의 최소공배수와 자연수 C의 최소공배수를 구해주면 A, B, C의 최소공배수를 얻을 수 있다.

위의 내용을 바탕으로 유클리드 호제법에 따라 최대공약수를 구한 후 최소공배수 = (비교군1 * 비교군2) / 최대공약수 공식으로 최소공배수를 구해주고, 처음 for문을 돌때는 미리 구해놓은 최소공배수가 없으므로 arr의 첫번째 원소와 두번째 원소를 통해 최소공배수를 얻을 수 있게 init이라는 불리언 자료형을 만들어주었다. 

코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(vector<int> arr) {
    
    int answer = 0;
    int result = 0;
    bool init = true;
    
    for (int i = 0; i < arr.size(); i++)
    {
        int a, b, temp;
        if (init)
        {
            if (arr[i] > arr[i + 1])
            {
                a = arr[i];
                b = arr[i + 1];
            }
            else
            {
                a = arr[i + 1];
                b = arr[i];
            }

            while (true)
            {
                temp = a % b;
                a = b;
                b = temp;

                if (temp == 0)
                {
                    result = (arr[i] * arr[i + 1]) / a;
                    break;
                }
            }

            i = 1;
            init = false;
        }
        else
        {
            if (result > arr[i])
            {
                a = result;
                b = arr[i];
            }
            else
            {
                a = arr[i];
                b = result;
            }

            while (true)
            {
                temp = a % b;
                a = b;
                b = temp;

                if (temp == 0)
                {
                    result = (result * arr[i]) / a;
                    break;
                }
            }
        }
    }

    return result;
}