적어도 대부분의 배수 [1145]

적어도 대부분의 배수 [1145]

백준 - https://www.acmicpc.net/problem/1145

1145번: 적어도 대부분의 배수

문제

• 다섯 개의 자연수가 있다. 이 수의 적어도 대부분의 배수는 위의 수 중 적어도 세 개로 나누어 지는 가장 작은 자연수이다.

• 서로 다른 다섯 개의 자연수가 주어질 때, 적어도 대부분의 배수를 출력하는 프로그램을 작성하시오.

 

---

입력

• 첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다.

출력

• 첫째 줄에 적어도 대부분의 배수를 출력한다.

   

 

---

풀이과정

• 최대공약수를 구하는 방법이 딱히 떠오르지 않아 찾아봤다.

• 호제법을 알게되었는데 상당히 유용한거 같아 이용하였다.

• 최대공약수를 구하면 최소공배수는 바로 구할수있다.

  • a*b/최대공약수 = 최소공배수

• 부분집합은 for 문을 통해서 구현하였다.

 

 

---

느낀점

• 처음에는 호제법이 와닷지는 않았는데 막상 실제수를 가지고 써보면 이해가된다.

• 좀 스킬(?) 이 필요한 문제였다.