글 읽기 - 분수 합 테스트 케이스 잘 돌아가는 것 같은데 어떤 이유로 틀렸다고 하는지..

uniform3000 7년 전 1

유클리드 호제법을 사용하지 않고 분모가 같으면 분모는 그대로 두고 분자 끼리 더해서 while문 돌아가게 분모가 다르면

분모 분자 곱하는 식으로 해서 통분 한 다음 while문 돌아가게 했어요. while 문에서 기약분수가 될 때 까지 분모 분자를 나눠주고 기약 분수가

되면 while 문 벗어나고 출력하도록 했는데 문제 테스트 케이스 이외에 엄청 큰 수를 넣어서 맞는 답인지 확인했는데도 불구하고 틀렸습니다

라고 하네요. 예외 테스트 케이스가 존재하는 건가요? 아니면 알고리즘 구현상 오류가 있는 부분이 있나요?

#include <stdio.h>

int main(){
	int a1,a2,b1,b2;

	scanf("%d %d %d %d",&a1,&a2,&b1,&b2);
	int n1,n2;
	if(a2 == b2){
		n1 = a1 + b1;
		n2 = a2;
	}else{
		n1 = a1*b2 + b1*a2;
		n2 = a2*b2;
	}

	// printf("n1: %d n2 : %d\n",n1,n2);

	int flag = 0;
	while(flag == 0){
		if(n2%n1 == 0){
			n2 = n2/n1;
			n1 = 1;
			flag = 1;
			break;
		}

		if(n1 % 2 == 0 && n2 % 2 == 0){
			n2 = n2/2;
			n1 = n1/2;
		}
		else if(n1 % 3 == 0 && n2 % 3 == 0){
			n2 = n2/3;
			n1 = n1/3;
		}
		else if(n1 % 5 == 0 && n2 % 5 == 0){
			n2 = n2/5;
			n1 = n1/5;
		}
		else if(n1 % 7 == 0 && n2 % 7 == 0){
			n2 = n2/7;
			n1 = n1/7;
		}
		else{
			flag = 1;
		}

		
	}
    
	printf("%d %d\n",n1,n2);

	return 0;
}

kesakiyo 7년 전 1

왜 2, 3, 5, 7에 대해서만 검사를 하시는 건가요?

입력으로 주어지는 수가 30000까지이기 때문에 (a / b + c / d)를 계산한

{(a * d + c * b) / (b * d)} 의 factor에는 당연히 7보다 큰 소수가 들어있을 수 있습니다.

30000까지 등장하는 모든 소수에 대해 if-else로 걸러주실게 아니라면 유클리드 호제법을 사용하시는게 정신건강에 좋을것 같네요...

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

문제

문제

출처

ICPC

분수 합 테스트 케이스 잘 돌아가는 것 같은데 어떤 이유로 틀렸다고 하는지..

uniform3000 7년 전 1

kesakiyo 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말