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

문제 설명

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

1934번: 최소공배수

 

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

백준 1934번 문제는 "최소공배수"라는 기본 배경지식에서 수학적 사고력을 요구하는 문제이다.

우리는 보통 최소공배수를 구하기 위해 아래와 같은 방법을 사용한다.

(ex) 10과 6의 최소공배수 구하는 방법

=> 2 * (5 * 3) = 30

 

여기에서 필자는 최대공약수라는 개념도 함께 개입하여 문제를 해결해보았다.

위의 예시에서, 10과 6의 최대공약수는 2이다.

최소공배수는 최대공약수와, 2개의 수를 각각 최대공약수로 나눈 값 2개와 함께 곱한 수라고도 할 수 있다.

여기에서 10 * 6 = (2 * 5) * (2 * 3) 과 같이 바꿀 수 있다.

따라서 최대공약수를 알아낸 뒤, 2개의 수를 곱한 값에 최대공약수로 한번 나누면 최소공배수를 구할 수 있다.

 

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

 

코드의 실행 순서

1) 테스트 케이스 및 각 케이스의 2개의 숫자(a, b) 입력받기

 

2) num 변수 선언한 뒤, 반복문을 통해 최대공약수(num) 구하기

(최대공약수가 없을 시 num은 1로 저장된 채로 진행한다.)

 

3) 입력받았던 a와 b를 곱한 값에 최대공약수 num으로 한 번 나누어, 최소공배수를 출력한다. 모든 테스트 케이스가 실행 완료되면 종료한다.

반응형

 

성공한 코드

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

//백준 1934번 코드
int main() {
	int n;
	scanf("%d", &n);

	int a, b;
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &a, &b);
		int num = 1;
		int a1 = a;	int b1 = b;
		for (int j = a1; j > 0; j--) {
			if (a1 % j == 0 && b1 % j == 0) {
				num *= j;
				a1 /= j; b1 /= j;
			}
		}
		printf("%d\n", a * b / num);
	}
}

 

제출 결과

(2021.12.16 백준 1934번 제출 결과)

(로직을 찾느라 아주 조금 헤맨 느낌이 있다.)