Life Engineering
[프로그래머스] N개의 최소공배수 (C++) 본문
https://programmers.co.kr/learn/courses/30/lessons/12953
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int gcd(int a, int b){
int a1=max(a,b);
int b1=min(a,b);
while (b1){
int c=a1%b1;
a1=b1;
b1=c;
}
return a1;
}
int lcm(int g, int a, int b){
return a*b/g;
}
int solution(vector<int> arr) {
int answer = 0;
int prev,g,l;
if (arr.size()==1)
return arr[0];
prev=arr[0];
for (int i=1; i<arr.size(); i++){
g=gcd(prev, arr[i]);
l=lcm(g, prev, arr[i]);
prev=l;
}
return l;
}
괜히 복잡하게 풀었다..
이 문제의 포인트는 2개 수의 최소공배수를 구해준 다음, 나머지 수와도 최소공배수를 계속 구해주는 방식이다.
다른 분의 풀이를 보니, (구한 최소 공배수, 나머지 수) 해서 바로 최소공배수를 구하는 방식을 취했다.
최소공배수는 두 수의 곱/최대공약수 이렇게 구해지므로, 최소공배수 함수 안에 최대공약수를 구하는 함수를 호출해야 한다.
최대공약수를 구하는 함수는 유클리드 호제법을 이용한다 (gcd(a,b)==gcd(b, a%b)), a>=b
유클리드 호제법 함수를 재귀로 구현할 수 있다.
'Problem Solving' 카테고리의 다른 글
[BOJ 1038] 감소하는 수 (C++) (0) | 2021.11.11 |
---|---|
[프로그래머스] 예상 대진표 (C++) (0) | 2021.11.11 |
[프로그래머스] 순위 (C++) (0) | 2021.11.05 |
[프로그래머스] 순위 검색 (C++) (0) | 2021.11.04 |
[BOJ 15654] N과 M(5) (C++) (0) | 2021.10.28 |