프로그래머스 - N개의 최소공배수 / C++

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12953

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

 

 

문제 풀이

2, 6, 8, 14의 최소 공배수를 구하기 위해서는 무조건 14의 배수가 되어야한다. 물론 2, 6, 8의 배수도 되어야 하지만 내가 떠올린 방식은 14의 배수가 되는 수들을 원소들로 모두 나누어보고, 나누어 떨어지면 최소공배수로 생각하였다.

 

그렇게 하기 위해서 주어진 vector를 내림차순으로 정렬하고 가장 큰 수를 임의의 정답으로 둔다.

for문을 돌며 모든 원소로 나누어 떨어진다면 answer를 리턴하고 그렇지 않다면 answer에 가장 큰 수를 계속 더해나갔다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

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

 

다른 풀이

a와 b의 최소 공배수는 (a*b) / (a와 b의 최대공약수) 라는 식이 알려져있다. 

이를 확장하여 n개의 원소를 가진 배열 arr = [ a, b, c, d ] 가 있을 때, 해당 공식을 함수로 구현하여

a와 b의 최소공배수를 구하고 그 값과 c의 최소공배수, 그 값과 d의 최소공배수를 구하면 해당 배열의 최소 공배수를 구할 수 있다.