[#19][알고리즘] N개의 최소공배수

프로그래머스 > N개의 최소공배수
문제링크(https://programmers.co.kr/learn/challenge_codes/152)

C++풀이

#include <iostream> #include <vector> #include <algorithm> using namespace std; //최대공약수 long long gcd(long long a, long long b){     return a%b==0 ? b : gcd(b, a%b); } //최소공배수 long long lcm(long long a, long long b){     return a*b/gcd(a,b); } long long nlcm(vector<int> num) {     long long answer = 0;     sort(num.rbegin(), num.rend());       answer =num[0];       for(int i = 1; i < num.size(); i++){         answer = lcm(answer,num[i]);     }     return answer; } int main() {     vector<int> test{ 2,6,8,14 };     // 아래는 테스트로 출력해 보기 위한 코드입니다.     cout << nlcm(test); } Colored by Color Scripter

cs

vector를 내림차순으로 정렬 => {14, 8, 6, 2}
-----------------------------------------------------
14와 8의 최소공배수 = 56
56과 6의 최소공배수 = 168
168과 2의 최소공배수 = 168
-----------------------------------------------------
i = 1 : lcm(14, 8) = 56 = answer
i = 2 : lcm(56,6) = 168 = answer
i = 3 : lcm(168,2) = 168 = answer
return answer = 168


나중에 다시 풀어보니 다른 풀이가 나와서 추가 (위에 풀이와 비슷하지만)

#include<iostream> #include<vector> using namespace std;   long long gcd(long long x, long long y) {     return x%y==0? y : gcd(y, x%y); }   long long nlcm(vector<int> num) {     long long answer = 0;     for(int i = 0; i < num.size()-1; i++){         if(i==0){             //처음 2와 6의 최소공배수를 구하기             answer = (num.at(i) * num.at(i+1)) / gcd(num.at(i), num.at(i+1));         }else{             //위에서 구한 2와 6의 최소공배수와 8의 최소공배수를 구하기             answer = (answer * num.at(i+1))/ gcd(answer, num.at(i+1));         }     }     return answer; }   int main() {     vector<int> test{2,6,8,14};       // 아래는 테스트로 출력해 보기 위한 코드입니다.     cout << nlcm(test); }   Colored by Color Scripter

cs