백준 14490 백대열: 문자열파싱/ 최대공약수 구하기

문제 :

문자열을 입력받아 정수로 변환하고 최대공약수를 구해 나누는 문제였다

입력

n과 m이 :을 사이에 두고 주어진다. (1 ≤ n, m ≤ 100,000,000)

ex) 10:1, 18:24

출력

두 수를 최대한으로 약분하여 출력한다.

 

작성코드

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int main()
{
	//입력 n:m	 n과m의 최대공약수로 나누기
	string inputNums;
	cin >> inputNums;
	//18:24  3:4 
	string A{}, B{};
	int a{}, b{}, grad{};
	//문자열을 ':'기준으로 잘라서 왼쪽을 a, 오른쪽을 b에 넣기
	A = inputNums.substr(0,inputNums.find(":"));
	B = inputNums.substr(inputNums.find(":") + 1,inputNums.size());
	a = stoi(A);
	b = stoi(B);
	//a,b중 더 큰 숫자에서 작은숫자를 나눴을때
	//나머지가 두 수의 최대공약수
	if ((a % b) == 0 or (b % a) == 0)
	{
		grad = min(a, b);
	}
	else
	{
		grad = max(a, b) % min(a, b);
	}
	//a,b를 최대공약수로 나누고 a:b 상태로 출력
	a /= grad;
	b /= grad;

	cout << a << ":" << b << endl;
	
	return 0;
}

 

출력은 정상적으로 나오지만 백준에서 정답인정이 되지않았다.

 

아마도 if문의 조건에서 a가 b의 배수일때만 계산하고 최대공약수를 구하는 과정에 문제가 있었던것 같다.

1. 유클리드 호제법을 이용해 최대공약수를 구하는 함수를 따로 만들자

2. max(a,b)에서 min(a,b)를 나누면 잘못된 결과가 생길수 도 있으니까 

    최대공약수를 구하는 함수를 만들고 그안에서 반복적으로 나머지를 구하자.

 

 

유클리드 호제법:  두 수 a,b 의 최대공약수는 큰 수 에서 작은 수를 나눈 나머지와 같다.

 

정의: 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.  (https://seunghyum.github.io/algorithm/Euclidean-algorithm/#)

 

수정 코드

 

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int gcd(int a, int b)
{
	while (b != 0)
	{
		int temp = b;
		b = a % b;
		a = temp;
	}
	return a;
}
int main()
{
	//입력 n:m	 n과m의 최대공약수로 나누기
	string inputNums;
	cin >> inputNums;
	//18:24  3:4 
	string A{}, B{};
	int a{}, b{}, grad{};
	//문자열을 ':'기준으로 잘라서 왼쪽을 a, 오른쪽을 b에 넣기
	A = inputNums.substr(0,inputNums.find(":"));
	B = inputNums.substr(inputNums.find(":") + 1,inputNums.size());
	a = stoi(A);
	b = stoi(B);
	//a,b중 더 큰 숫자에서 작은숫자를 나눴을때
	//나머지가 두 수의 최대공약수
	grad = gcd(a, b);
	//a,b를 최대공약수로 나누고 a:b 상태로 출력
	cout << a / grad << ":" << b / grad << endl;
	
	return 0;
}