[백준 2609번] 최대공약수와 최소공배수

 

www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

[문제]

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

 

<알고리즘 분류> 수학, 정수론, 유클리드 호제법

 

[input]

첫째 줄에는 두 개의 자연수가 주어진다.

  이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

[output]

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

---

 

 

---

 

[풀이 방법]

- 최소공배수와 최대공약수에 대한 함수 작성하여 간소화시킴

    - 최대 공약수

        - 큰 수에서 작은 수 나누었을 때 나머지가 0인 경우 작은 수가 최대공약수

        - 나누어 떨어지지 않는 경우, 작은 수는 큰 수로, 나머지를 작은 수로 바꾸는 방법 반복

    - 최소 공배수

        - 두 수의 곱 / 최대공약수

 

1. Scanner 사용

2. 최대 공약수와 최소 공배수에 대한 함수 작성

3. 두 수 입력받아 각각 변수 A와 B에 저장

4. 최대공약수 함수에 매개변수로 큰 수와 작은 수 순서로 넣어주어 연산

5. 최소공배수 함수에 두 수와 최대공약수를 추가해주어 연산

6. 최대공약수와 최소공배수를 각 한 줄씩 출력

 

---

 

성공 코드