[백준 BOJ] 2609번 최대공약수와 최소공배수 (C언어)

문제 설명

https://www.acmicpc.net/problem/2609

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

 

접근 방법 - 수학적 사고력을 요구하는 문제

백준 2609번 문제는 최소공배수와 최대공약수의 배경지식에서 수학적 사고력을 요구하는 문제이다.

위 2가지의 개념을 이전 글에서도 다룬 적이 있으니 아래의 링크를 참고해보길 바란다.

https://smary-it.tistory.com/18

[백준 BOJ] 1934번 최소공배수 (C언어)

다만 위 문제의 조건과는 다른 점이 있다면, 두 수 중에서 먼저 입력되는 숫자가 더 작다는 전제가 없다.

따라서 여기에서 추가적으로 보완하여 코딩을 진행하였다.

필자는 아래의 순서대로 코드를 작성하며 문제를 해결하였다.

 

코드의 실행 순서

1) 두 수(a, b)를 입력받는다.

 

2) min을 선언하여, a 또는 b 중 더 작은 수의 값을 min에 저장한다.

 

3) num, a1, b1을 각각 선언하여 아래처럼 초기화한다.

- num: 최대공약수를 저장하는 변수, 1로 초기화한다.

- a1: a의 값을 임시적으로 저장하는 변수

- b1: b의 값을 임시적으로 저장하는 변수

 

4) 반복문을 실행한다.

- 반복문의 제어 변수 i는 min에서부터 1까지 1씩 감소하는 변수로 설정한다.

- 만약 a1과 b1이 i로 모두 나누어 떨어질 때, num에 i를 곱하고, a1과 b1을 i로 나눈다.

(여기서, a1과 b1을 따로 선언한 이유는 a, b 값은 유지해야 하기 때문이다.)

 

5) 연산이 모두 끝나면, 최대공약수와 최소공배수를 순차적으로 출력하고 실행 종료한다.

(연산을 아래처럼 한 이유는 위의 1934번 링크 설명을 참고하길 바란다.)

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <stdio.h>

//백준 2609번 코드
int main() {
	int a, b;
	scanf("%d %d", &a, &b);

	int min;
	if (a > b) { min = b; }
	else { min = b; }

	int num = 1;
	int a1 = a;	int b1 = b;
	for (int i = min; i > 0; i--) {
		if (a1 % i == 0 && b1 % i == 0) {
			num *= i;
			a1 /= num;	b1 /= num;
		}
	}

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

 

제출 결과

(2021.12.17 백준 2609번 문제 제출 결과)