정수론 및 조합론 - 2609번

2월 6일(월) - 정수론 및 조합론(2609번)

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

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

x

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

(160ms -> 바람직하지 못한 풀이인듯 / 차라리 풀이 - 2가 나음)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int main(void)
{
	int first, second;
	scanf("%d %d", &first, &second);

	int g_c_d = 0;
	for (int i = 1; i <= first && i <= second; i++)
	{
		if (first % i == 0 && second % i == 0) {
			g_c_d = i;
		}
	}

	printf("%d\n", g_c_d);
	printf("%d", first * second / g_c_d);

	return 0;
}

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

(유클리드 호제법 - 230227 추가)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int GCD(int a, int b)
{
	if (b == 0)
	{
		return a;
	}
	else
	{
		return GCD(b, a % b);
	}
}

int LCM(int a, int b)
{
	return (a * b) / GCD(a, b);
}

int main(void)
{
	int a, b;
	scanf("%d %d", &a, &b);

	printf("%d\n", GCD(a, b));
	printf("%d", LCM(a, b));

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ