[백준 BOJ] 2702번 초6 수학 (C++/cpp)

문제 설명

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

2702번: 초6 수학

 

접근 방법 - 최대공약수와 최소공배수 연산의 기본 문제

백준의 2702번 문제는 최대공약수 및 최소공배수에 대한 연산을 통해 해결해야 하는 문제이다.

해당 문제는, 각 케이스마다 주어지는 두 숫자의 최소공배수와 최대공약수를 출력해야 하는 문제이다.

이 문제의 알고리즘 카테고리를 참고하면, 사칙연산과 브루트포스 알고리즘을 주로 응용하여 해결해야 하는 것으로 보인다.

아래에 이와 유사한 문제의 풀이에 대하여 이전에 작성한 글의 링크들이 있으니 이를 함께 참고하는 것도 좋을 것이다.

사실상 연산하는 방법에 대한 코드 부분은 거의 같을 것이다.

(1934번 최소공배수 문제의 풀이도 함께 기재하니 이것도 함께 참고해보길 바란다.)

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

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

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

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

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.

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

 

코드의 실행 순서

1) 테스트 케이스의 수(n)를 입력받는다.

 

2) n의 크기만큼 반복문을 실행하여 아래의 연산을 취한다.

- 2개의 숫자(a, b)를 입력받는다.

- 최대공약수를 저장할 변수 num을 1로 초기화하여 선언한다.

- 변수 min을 선언해 a와 b 중 작은 값을 저장하여 선언한다.

- min부터 2까지(j) 하여 a와 b에 대하여 각각 나머지 연산을 수행해본다.

만일 두 숫자 모두 j에 나누어 떨어진다면, a와 b를 각각 j로 나눈 몫으로 저장해둔다.

그리고 현재 j가 두 숫자에 모두 나누어 떨어지는 숫자이기 때문에 num에 j를 곱해둔다.

 

3) 현재 num에는 a와 b에 대한 최대공약수가 저장되어있으며 a와 b에는 num으로 나누었을 때의 몫이 저장되어있다.

여기서 입력받은 2개의 값에 대한 최소공배수는 현재의 a와 b와 최대공약수인 num을 모두 곱한 값이다.

이에 따라서 최소공배수를 출력한 뒤, 잇따라 최대공약수인 num도 함께 출력한다.

 

4) 출력이 모두 수행되었다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 2702번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;

		int num = 1;
		int min = a < b ? a : b;
		for (int j = min; j > 1; j--) {
			if (a % j == 0 && b % j == 0) {
				a /= j;	b /= j;
				num *= j;
			}
		}
		cout << a * b * num << " " << num << endl;
	}
}

 

제출 결과

(2022.06.02 백준 2702번 문제 제출 결과)