[C++] 프로그래머스 :: N개의 최소공배수

안녕하세요 뚜디 입니다 :)

코딩테스트 연습 - N개의 최소공배수 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - N개의 최소공배수

< 프로그래머스 - N개의 최소공배수 (LV2) >

---

1. 연습 문제

2. 문제 풀이

3. 소스 코드

4. 결과

---

1. 연습 문제

• 문제 설명

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

• 제한 조건

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

• 입출력 예

arr	result
[2,6,8,14]	168
[1,2,3]	6

 

2. 문제 풀이

이번 문제는 임의의 정수 여러개의 최소공배수를 구하는 문제입니다.
(이때, 정렬된 상태로 입력이 되는건지 정렬이 안된 상태로 입력이 되는건지는 테스트결과 정렬된상태로 입력)

1. 입력된 벡터(정렬된) arr의 마지막 인자부터 무한루프의 반복문을 생성
2. 입력된 벡터 arr의 인자값들이 모두 나누어 떨어지는 수를 찾아 리턴한다.

 

3. 소스 코드

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

using namespace std;

int solution(vector<int> arr) {
    int count = 0;
    
    for (int i = arr.back(); ; i++) {
        for (int j = 0; j < arr.size(); j++) {
            if (i % arr[j] == 0) {
                count++;
            } else {
                count = 0;
                break;
            }

            if (count == arr.size()) {
                return i;
            }
        }
    }

    return -1;
}

 

4. 결과