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



문제 풀이 정보




문제

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

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000 이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.



작성한 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>

int main() {
int a, b, mid;

scanf("%d %d", &a, &b);

if (a > b)
mid = b;
else
mid = a;

while (!((a % mid == 0) && (b % mid == 0))) {
mid -= 1;
}

printf("%d\n%d\n", mid, mid * (a / mid) * (b / mid));

return 0;
}



출력 결과




메모

가장 먼저 두 개의 자연수를 표현할 정수형 변수 a, b와 최대 공약수를 찾기 위해 mid라는 정수형 변수를 선언하였다. a와 b에 자연수를 입력받게 되면 그 중 더 작은 값을 임시로 mid 변수에 대입하여 최대공약수를 찾을 준비를 한다.

while 문에 들어간 후, a를 mid로 나누었을 때와 b를 mid로 나누었을 때 각각의 나머지 값이 0이 될 때 까지 mid의 값을 하나씩 줄여가도록 하였다. 이는 a와 b 둘 중 더 작은 값이었던 mid를 하나씩 줄여가면서 두 자연수가 공통으로 나누어지는 수 중 가장 큰 수를 찾게 되면 그 값(최대공약수)은 mid에 저장 되고 while문은 탈출할 수 있도록 하는 구조이다. 이렇게 최대공약수를 찾게 되면 그 값을 이용하여 mid * a를 mid로 나눈 값 * b를 mid로 나눈 값을 계산한 최소공배수 또한 얻어낼 수 있다.

처음 문제를 접하고 최대공약수를 빼내는 과정을 생각해내는 것이 약간 어려웠지만 결과적으로 해당 값들로부터 기준점을 잡고, 그것을 이용하여 값을 변화시키고 비교하면서 문제를 풀 수 있었다.

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

https://y8ncastle.world/2018/04/02/boj/2609-c/

Author

Alec J

Posted on

2018-04-02

Updated on

2021-02-09

Licensed under