글 읽기 - 시간초과좀 해결해주시면 감사하겠습니다.

keepyourweaponaimed 4년 전 0

각 기능에 대해서 주석을 달아놓았습니다.

어느 부분에서 시간초과가 유발되는지 알려주시면 감사하겠습니다.

아니면 두 수에서 약수를 동시에 찾겠다는 로직 자체가 시간초과를 유발하는 것일까요?

main(){
  int a, b, c, d, res1, res2, cnt1 = 0, cnt2 = 0, rescnt = 0;
  int arr1[1001] = {}, arr2[1001] = {}, f[1001] = {};
  scanf("%d %d", &a, &b);
  scanf("%d %d", &c, &d);

  /*res1은 분자, res2는 분모*/
  res1 = a * d + c * b;
  res2 = d * b;

  /* 약수 구하는 파트 */
  for(int i=1; i<=res1; i++){
    if(res1 % i == 0) arr1[cnt1++] = i;
  }
  for(int i=1; i<=res2; i++){
    if(res2 % i == 0) arr2[cnt2++] = i;
  }

  /* res1과 res2중에 같은 약수가 있으면 f배열에 넣음*/
  for(int i=0; i<cnt1; i++){
    for(int j=0; j<cnt2; j++){
      if(arr1[i] == arr2[j]) f[rescnt++] = arr1[i];
    }
  }
  rescnt = 0;

  /* f배열에 몇개나 들어가있는지 체크*/
  for(int i=0; i<1001; i++){
    if(f[i] == 0) break;
    rescnt++;
  }

  /* 큰거부터 나눠주는데, res1과 res2에 동시에 나눠진다면 나눔.*/
  for(int i=rescnt-1; i>0; i--){
    if(f[i] != 1){
      if((res1 % f[i] == 0) && (res2 % f[i] == 0)){
        res1 = res1 / f[i];
        res2 = res2 / f[i];
      }
    }
  }
  printf("%d %d", res1, res2);
}

james_kylee 4년 전 0

곱셈으로 통분 한 다음에 최대공약수로 나눠주세요. 아래는 유클리드 호제법을 이용한 최대공약수 구하는 함수입니다.

int gcd (int a, int b) {
    return b ? gcd(b, a % b) : a;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과좀 해결해주시면 감사하겠습니다.

keepyourweaponaimed 4년 전 0

james_kylee 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말