백준 14490 - 백대열(C++)

문제

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

14490번: 백대열

풀이

주어진 숫자 2개를 최대한 약분하여 출력하는 문제이다.

입력이 n:m의 형태로 주어지기 때문에 문자열로 입력받아서 : 를 기준으로 자른 후, 최대공약수를 구해야 한다.

sstream 헤더만 입력하면 문자열 파싱과 문자열을 int로 바꾸는 것까지 가능하다.

두 수를 최대한 약분하려면 두 수의 최대공약수로 나눠주면 된다.

최대공약수는 유클리드 호제법으로 구할 수 있다.

두 숫자가 나누어 떨어지거나, 0이 될 때까지 나머지 연산을 반복하다 보면 최대공약수를 구할 수 있다.

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;


int eculidean(int a, int b)
{
    int n=a;
    while(n>0)
    {
        if(n%b==0) return b;
        else
        {
            int tmp=n%b;
            n=b;
            b=tmp;
        }
    }
    return 1;
}

int main()
{
    string str;
    cin>>str;
    istringstream ss(str);
    string stringbuffer;
    vector<string> v;
    while(getline(ss,stringbuffer,':'))
    {
        v.push_back(stringbuffer);
    }
    int a,b;
    stringstream ssInt1(v[0]);
    ssInt1>>a;
    stringstream ssInt2(v[1]);
    ssInt2>>b;
    int t = eculidean(a,b);
    cout<<a/t<<":"<<b/t;
}