문제 설명

문제 출처

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다.

예를 들어 2와 7의 최소공배수는 14가 됩니다.

정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다.

n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.

• arr의 원소는 100 이하인 자연수입니다.

예제 입출력

Solution

수학 알고리즘에서 자주 출제되는 최소 공배수 구하기 문제이다. 다만 이 문제는 배열 내의 모든 수의 최소공배수를 구하는 문제로써, 어떻게 보면 최소공배수 알고리즘 공식을 배열 요소들 모두에 적용해야 한다고 생각할 수 있다.

공배수라는 말 뜻 자체를 생각해본다면 나누었을때 나머지가 0이 되어야 한다는 당연한 사실을 알 수 있다.

즉, 주어진 배열에서 각 요소들이 0으로 나누어 떨어진다면 그 수가 요소들의 공배수의 자격을 갖는다.

그리고 최소 공배수를 구하기 위해서는 요소들 중 가장 큰 값을 기준으로 하는 것이 좋다.

위 예제 입출력에서 [2, 6, 8, 14]와 같이 요소들이 주어졌다면 가장 큰 수인 14를 기준으로 나누어 떨어지는지를 확인하려면 14에 1, 2, 3 … 과 같이 1씩 증가하는 값들을 곱한 후 그 값이 나머지 요소들로 나누어 떨어지는지를 확인한다.

가장 큰 값을 기준으로 하는 이유는 최소한의 횟수로 계산을 하기 위해서 이다.

코드는 아래와 같다.

Code

Flag를 사용하는 이유는 각 요소들이 모두 0으로 나누어떨어졌는지를 확인하기 위한 플래그로써, 하나라도 나누어 떨어지지 않는다면 그 다음 곱한 값에 대한 계산을 진행한다.

몇줄 평

수학적 접근이 흥미로운 문제였음.

참고 및 출처