BaekJoon 14786 Ax+Bsin(x)=C 2

Link https://www.acmicpc.net/problem/14786

소스결과 1132 KB 16ms

출처 Baekjoon 

언어 C++ 17

분류 이분 탐색

 

설명

A, B, C가 주어졌을 때, Ax + Bsin(x) = C를 만족하는 x를 찾아야 한다.

 

정말 잘 구한거 같은데 왜 틀리는지 알 수 없던 문제.

맞은 사람도 많지 않고 질문도 많지 않았다. tc로 사용했던 것도 다 맞았는데 너무 많이 틀렸었다.

알고리즘은 단순하다. x로 생각 할 수 있는 범위의 값 중에서 중간 값을 골라 수식의 결과 값이 C와 어떤 관계가 있는지를 판단해 이분 탐색을 진행한다.

범위를 long double로 확장해 부동소수점의 정확성 범위를 늘려야한다.

이진 탐색만 구현하면 된다.

 

알고리즘

1. A, B, C를 입력 받는다.

2. 이진 탐색 범위를 C - B ~ C + B 까지로 설정한다 ( sin(x)의 값이 -1 ~ + 1 까지이기 때문 )

3. 최소 범위와 최대 범위가 역전되기 전까지 반복한다.

 3 - 1. 범위의 중간값을 구한다.

 3 - 2. 범위의 중간값과 sin(x)에 x에 mid에 대입한 x의 값을 구한다. ( Ax 의 x를 구하는 과정 )

 3 - 3. 3 - 2 의 값과 중간값을 비교해 크면 최대 범위를, 작으면 최소 범위를 축소 시킨다.

4. 소수점 19자리까지 출력한다.

 

소스코드 < 본 소스코드는 여러 Github 을 참고했습니다. >

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <math.h>

using namespace std;

int main()
{
	int  a, b, c;

	scanf("%d %d %d", &a, &b, &c);

	long double to = (c - b) / (double)a;
	long double des = (c + b) / (double)a;
	long double mid;
	int stopper = 50000;

	while (to < des && stopper--)
	{
		mid = (des + to) / 2;
		
		if (mid > (c - (b * (long double)sin(mid))) / a)
			des = mid;
		else if ( mid < (c - (b * (long double)sin(mid))) / a)
			to = mid + 0.00000000000000000001;
	}

	printf("%.19Lf\n", mid + 0.00000000000000000005);

	return 0;
}