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
'Algorithm > Programers - C++' 카테고리의 다른 글
[프로그래머스] 이진 변환 반복하기 (0) | 2023.08.26 |
---|---|
[프로그래머스] 배달 / 다익스트라 알고리즘 (0) | 2023.08.13 |
[프로그래머스] 공원 산책 - Tuple (0) | 2023.08.06 |
[프로그래머스] 이진수 더하기 (0) | 2023.07.29 |
[프로그래머스] 바탕화면 정리 (0) | 2023.07.23 |