글 읽기 - 왜 시간초과가 날까요... ㅠ

kim031504 4년 전 0

저 while 반복문을 돌리면서

2의 거듭제곱인지 판별하는 과정에서 시간초과가 나는 듯한데,

좀 더 개선할 수 있는 방법 없을까요...? ㅠ

코드에 대한 자세한 설명은 주석으로 달아놨습니다!

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
	int A, B, C;

	cin >> A >> B >> C;


	// 루트 안의 판별식을 담는다.
	int judge = (int)pow(B, 2) - (4 * A*C);


	// 중근이거나 허근이면 "둘다틀렸근"을 출력하고 함수 종료!
	if (judge == 0 || judge < 0)
	{
		cout << "둘다틀렸근" << endl;
		return 0;
	}

	
	// 근의 공식을 이용하여 해를 구한다.
	int n1 = (-1)*B + sqrt(pow(B, 2) - (4 * A*C));
	int n2 = (-1)*B - sqrt(pow(B, 2) - (4 * A*C));

	n1 /= (2 * A);
	n2 /= (2 * A);

	// 소수점을 가지는 실수근이 하나라도 존재한다면
	if ((n1 - int(n1) > 0) || (n2 - (int)n2 > 0))
	{
		cout << "정수근" << endl;
		return 0;
	}


	// 3.0 이런 식의 값을 3과 같이 정수화 시킨다.
	n1 = (int)n1;
	n2 = (int)n2;


	// 2의 제곱꼴이 아닌지 판단하는 변수이다.
	int count = 0;


	// 2로 계속 나눠 1이 되지 않을 때까지
	while (n1 != 1)
	{

		// 과정에서 하나라도 2로 나누어떨어지지 않는 구간이 발생하면
		if (n1 % 2 != 0)
		{
			// 카운트 증가시키고
			count++;
			// 반복문 탈출!
			break;
		}

		n1 /= 2;
	}


	// n2에 대해서도 마찬가지
	while (n2 != 1)
	{
		if (n2 % 2 != 0)
		{
			count++;
			break;
		}

		n2 /= 2;
	}


	// 두 해의 2의 제곱꼴 판별 과정을 거쳐 다 통과했으면 "이수근"출력
	if (count == 0)
	{
		cout << "이수근" << endl;
	}
	// 아니면 "정수근"출력
	else
	{
		cout << "정수근" << endl;
	}

	return 0;
}

wookje 4년 전 1

제가 술 ㅁ거어서 코드는 못 읽겠지만 방적식 해의 절댓값이 100을 넘지 않음을 알 수 있어요 그래서 다 넣어보면 돼요

inc5025 4년 전 1

n1, n2의 자료형이 int이니, 실수인 값을 재대로 받아들일 수 없습니다.
소수점을 가지는 실수근이 하나라도 존재한다면 '정수근'이 아닌 '둘다틀렸근'입니다.
n1, n2의 자료형이 int이니 실수근 체크를 그냥 넘어갑니다. 만약 6 -5 1같은 인풋이 들어와서 n1이 0이 되면 50번째 while문에서 무한 루프를 돌게 됩니다.

kim031504 4년 전 1

우와! 제가 그 부분까지 생각을 못 했네요! 다시 풀어보겠습니다! 감사합니다!

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

문제

문제

출처

ICPC

왜 시간초과가 날까요... ㅠ

kim031504 4년 전 0

wookje 4년 전 1

inc5025 4년 전 1

kim031504 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말