백준14490 백대열

작성일 | In

문제 링크

  • http://icpc.me/14490

문제 출처

  • 2017 선린 봄맞이 대회 D번

사용 알고리즘

  • 유클리드 호제법

시간복잡도

  • O(log( Max(n, m) ))

풀이

최대한 약분한다 라는 것은 최대 공약수로 나눈다 와 같은 의미입니다.
유클리드 호제법을 이용하여 gcd를 구한 뒤 적절히 나누어서 출력하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>

int gcd(int a, int b){
    if(!b) return a;
    gcd(b, a%b);
}

int main(){
    int g;
    int a, b; scanf("%d:%d", &a, &b);
    g = gcd(a, b);
    printf("%d:%d", a/g, b/g);
}