본문 바로가기

Algorithm/Programers - C++

[프로그래머스] N개의 최소공배수 / 유클리드 호제법

 

Level. 2

 

문제

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다.
예를 들어 2와 7의 최소공배수는 14가 됩니다.
정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다.
n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

* 제한 사항
- arr은 길이 1이상, 15이하인 배열입니다.
- arr의 원소는 100 이하인 자연수입니다.

 

풀이

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

/*
GCD = 최대공약수
LCM = 최소공배수
*/
int gcd(int n, int m){
    if(n%m == 0) return m;
    return gcd(m, n%m);
}

int solution(vector<int> arr) {
    int answer = 0;
    int num = arr[0]; // 이전에 구한 최소공배수
    for(int i=1; i<arr.size(); i++){
        int g = gcd(num, arr[i]); // 최대공약수
        num = num*arr[i]/g; // 최소공배수
    }
    return answer = num;
}

 

해결 방법

 

배열을 순회하면서

1. 유클리드 호제법을 사용하여 두 수(직전에 구했던 최소공배수와 현재값)의 최대공약수(GCD)를 구한 후

2. 두 수를 곱한값을 최대공약수로 나누어 최소공배수를 구한다. 

 


다른 풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int gcd(int x, int y) { return x % y == 0 ? y : gcd(y, x % y); }
int lcm(int x, int y) { return x * y / gcd(x, y); }
int solution(vector<int> arr) {
    int answer = arr[0];
    for (int i = 1; i < arr.size(); i++)
        answer = lcm(answer, arr[i]);
    return answer;
}

 

 


https://school.programmers.co.kr/learn/courses/30/lessons/12953?language=cpp 

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr