12953: N개의 최소공배수

Link : programmers.co.kr/learn/courses/30/lessons/12953

---

1. 문제

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

---

2. 문제의 조건

• 1 <= length <= 15
• value <= 100

 

---

3. 문제 접근

• 시간 복잡도
  
  추후 보강

 

• 아이디어
  
  최소 공배수의 아이디어 상 2~ 나누어 질 수 있는 수는 모두다 나누어 준 다음 나누어진 값들의 곲으로 표현할 수 있습니다.
  
  

  2	3	4	9	16
  2	3	2	9	8
  2	3	1	8	4
  2	3	1	9	2
  3	3	1	9	1
  3	1	1	3	1
  	1	1	1	1

  다음과 같이 보시면 3 4 9 16을 예시로 들면, 2로 나누어떨어지는 수는 전부 나누면서 2를 추가합니다.
  3 1 9 1 단계에서 더이상 2로 나누어 떨어지는 수가 없을 떄, 3으로 나누어봅니다.
  이런 단계를 계속 밟으면서 맨 왼쪽에 있는 공배수들의 값을 곱해주면 정답이 됩니다.

 

---

4. 풀이 방법

• 제일 큰값을 정해두고 2부터 제일 큰 값 까지 나누기를 시도합니다.
• 만약 arr[item]가 i로 나누어 떨어진다면 그것으로 다 나눈 다음, 한번이라도 나누어 떨어졌으니 stack에 추가하고 한번 더 2로 나누어봅니다.
• 해당 문제는 구현력이 필요한 문제이므로 깊게 설명하지 않겠습니다.

 

---

5. 소스코드

• cjw-git.tistory.com/110

---

 

cjw.git@gmail.com