Bronze 2609

첫시도

#include <iostream>
using namespace std;

int arr[9999];
int main() {
	int a, b, max = 1, min = 10000;
	cin >> a >> b;

	for (int i = 2; i <= 10000; i++) {
		if (a%i==0&&b%i==0) {
			max = i;
		}
	}
	for (int i = 10000; i > 0; i--) {
		if (i % a == 0 && i % b == 0) {
			min = i;
		}
	}
	cout << max << '\n';
	cout << min;

	return 0;
}

답은 나오는데 틀렸습니다가 뜬다
유클리드 호제법을 이용하여 풀었다.

두번째 시도

#include <iostream>
using namespace std;


int f(int a, int b) {
	int tmp;
	while (1) {
		tmp = a % b;
		if (tmp == 0) {
			return b;
		}
		a=b;
		b = tmp;
		
	}
}

int main() {
	int a, b,min=0,max=0;
	cin >> a >> b;
	if (a > b) {
		min = f(a,b);
	}
	else {
		min = f(b, a);
	}
	max = (a * b) / min;
	cout << min << '\n'<<max;
	return 0;
}

풀이)

1. a,b중 큰 수를 찾습니다.
2. 유클리드 호제법을 이용하여 최대공약수를 구합니다.
3. 두 수의 곱 = 최대공약수 X 최대공배수를 이용하여 최대 공배수를 구합니다.

Bronze 1934

첫시도

#include <iostream>
using namespace std;

int f(int a,int b) {
	if (a < b) {
		int tmp1 = a;
		a = b;
		b = tmp1;
	}
	int tmp;
	while (1) {
		tmp = a % b;
		cout << 'a';
		if (tmp == 0) {
			return b;
		}
		cout << 'b';
		b = tmp;
		a = b;
	}
}
int main() {
	int N,a,b;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		cout <<  f(a, b) << '\n';
	}
	return 0;
}

논리 오류상 틀린게 없는 것 같은데 답이 정확하게 안나온다.

두번째 시도

#include <iostream>
using namespace std;

int f(int a,int b) {
	if (a < b) {
		int tmp1 = a;
		a = b;
		b = tmp1;
	}
	int tmp = a % b;
	if (tmp == 0) {
		return b;
	}
	else return f(b, tmp);
}
int main() {
	int N,a,b;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		cout <<  a*b/f(a, b) << '\n';
	}
	return 0;
}

유클리드 호재법을 반복문으로 풀수도 있지만 재귀함수로도 풀어보았다.