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

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

프로그래머스

 

전체 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> arr) {
    int answer = 0;
    sort(arr.begin(),arr.end(),greater<>());
    for(int i=arr[0];;i+=arr[0])
    {
        bool flag = false;
        for(int j=1;j<arr.size();j++)
        {
            if(i%arr[j]!=0)
            {
                flag=true;
                break;
            }
        }
        if(flag==false)
        {
            answer=i;
            break;
        }
        
    }
    
    
    return answer;
}

 

풀이 방법

최소 공배수는 일단 제일 큰 수의 배수가 될 수 밖에 없다.

그래서 제일 큰 수의 배수를 반복문으로 돌며

모든 요소들로 나눠봤을때 딱 떨어진다면 이것은 모든 요소의 배수이자 최소 공배수이다.

 

sort(arr.begin(),arr.end(),greater<>());

 제일 큰 수를 찾기위해 내림차순으로 정렬을 했다.

 

for(int i=arr[0];;i+=arr[0])
{
	...
}

i는 제일 큰 수부터 시작하여 배수로 올려갈것이다.

 

 bool flag = false;
        for(int j=1;j<arr.size();j++)
        {
            if(i%arr[j]!=0)
            {
                flag=true;
                break;
            }
        }

flag는 어떤 요소가 나누어 떨어지지 않는다면 false로 바뀔것이다.

반복문은 제일 큰 수를 제외하여 나누어 볼거기 때문에 인덱스 1부터 끝까지 돈다.

 

        if(flag==false)
        {
            answer=i;
            break;
        }

모든 요소를 돌았는데 false라면

모든 요소가 나누어 떨어진다는 소리고

지금의 i가 최소 공배수가 된다.