문제
https://school.programmers.co.kr/learn/courses/30/lessons/12953
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int getGCD(int n1, int n2) {
int tmp;
while(true) {
if((n1 % n2) == 0) return n2;
tmp = n1;
n1 = n2;
n2 = tmp % n2;
}
}
int solution(vector<int> arr) {
int answer = 0;
answer = arr[0] * arr[1] / getGCD(max(arr[0], arr[1]), min(arr[0], arr[1]));
for(int i=2; i<arr.size(); i++) {
answer = answer * arr[i] / getGCD(max(answer, arr[i]), min(answer, arr[i]));
}
return answer;
}
풀이
두 수의 최소공배수는 두 수의 곱 / 최대공약수 이다.
최대공약수를 구할 때에는 유클리드 호제법을 이용하였다.
처음 두 수의 최소공배수를 answer 에 저장한 뒤에 다음 수부터 answer 와 배열의 수의 최소공배수를 단계적으로 구했다.