[BOJ/C++] 13705. Ax+Bsin(x)=C

 

문제 : https://www.acmicpc.net/problem/13705

13705번: Ax+Bsin(x)=C

 

1. 설명

정수 A, B, C가 주어집니다. 문제의 제목대로, Ax + Bsin(x) = C를 만족하는 x의 값을 구해야 됩니다.

거의 똑같은 문제로 14786번 문제가 있습니다.

둘 다 같은 식의 해 x를 구하는 것이지만,

13705번은 $10^{-7}$의 자리에서 반올림해야 하고, 14786번은 그냥 구하면 됩니다.

스페셜 저지냐 아니냐도 갈리는데, 이러한 차이만으로 난이도가 극단적으로 바뀌었습니다.

너무 헤매는 바람에 20트를 더 한 뒤에 Python으로 먼저 풀었습니다.

인생 처음으로 Python으로 풀어본 백준 문제가 되겠네요.

 

2. 풀이

먼저 14786번을 기준으로 풀어봅시다.

$f(x) = Ax + Bsin(x)$에 대해 특별히 유도할 수 있는 x에 대한 성질이나 식은 없어 보입니다.

다만 미분을 통해 $f'(x) = A + Bcos(x)$이고, $0 < B \le A$이므로 항상 $f'(x) \ge 0$임을 알 수 있습니다.

따라서 $f(x)$는 증가함수입니다.

 

이를 이용하여 해를 근사적으로 구해야 합니다. 이분 탐색을 하거나, 뉴턴법을 사용하면 됩니다.

여기서는 이분 탐색을 사용하겠습니다.

$Ax - B \le Ax + Bsin(x) = C \le Ax + B$이므로, $\frac{C-B}{A} \le x \le \frac{C+B}{A}$입니다.

따라서 $l = \frac{C - B}{A}, R = \frac{C + B}{A}$로 두고 이분 탐색을 실행하면 됩니다.

 

혹은, $A * 0 + B * sin(0) = 0 < C$이고,

$sin(100000) > 0$이므로 $C \le 100000 < 100000A + sin(100000) * B$가 성립하여

$l = 0, r = 100000$으로 두고 시작해도 상관없습니다.

실수해를 구하는 것이므로 자료형은 double을 사용합니다.

 

14786번은 이렇게 풀면 AC를 받을 수 있습니다.

하지만 문제는 13705번인데, 10^-7의 자리에서 반올림하는 것이 부동 소수점에서 나타나는 오차때문에 값이 잘 못 나올 수 있습니다.

 

예를 들어 실제 해가 $x = 0.3453004999999999991354...$ 정도로 나왔다면,

출력해야 하는 답은 10^-7의 자리의 4를 반올림하여 0.345300을 출력해야 합니다.

그런데 오차때문에 구한 해의 근사치 $x' = 0.34530050000000...$으로 나올 수 있으며 이 값을 반올림하면

결과는 0.345301로 나오게 됩니다. 이런 경우가 일일히 채점 데이터로 기록되어 있는 탓에

14786번을 그대로 13705번에 제출하면 WA를 받게 됩니다.

 

해결 방법은 더 표현이 정확한 실수형 타입을 사용하는 것 밖에는 없습니다.

 

C/C++에서는 16바이트 실수형으로 __float128이 있습니다.

__float128 PI = 3.14159265358979323846264338327950288419716939937510q;

다만 __float128는 gcc 컴파일러에서 지원하며, Visual Studio에서는 지원하지 않는 것 같습니다.

경우에 따라 long double이 16바이트 실수형 타입으로 지원될 수도 있습니다.

 

혹은 Python, C# 등에서 Decimal 클래스를 사용할 수 있습니다. 계산할 소수점 아래 자릿수를 지정할 수 있습니다.

ex) Precision = 50으로 하여 소수점 아래 50자리까지 계산할 수 있습니다.

 

두 가지 경우 모두 sin 함수가 그 만큼의 정확도를 보장하지 않기 때문에 sin 함수를 직접 구현해야 합니다.

저는 이 과정에서 문제가 많이 발생해서 Python으로 풀고 C/C++ 풀이를 참고해야 했습니다.

 

sin 함수는 테일러 급수 형태로 $sin(x) = \sum^{\infty}_{n=0} \frac{(-1)^nx^{2n+1}}{(2n+1)!}$ 입니다.

n의 크기가 클 수록 sin(x)의 정확도가 올라가기 때문에, 충분한 만큼 반복해서 값을 구해주시면 됩니다.

보아하니 n = 32 정도면 충분히 돌아가는 것 같습니다.

sin(x) //pseudo code
{
    ret = x;
    term = x;
    x2 = -x * x;
    for (int i = 2; i <= n; i += 2)
    {
    	term *= x2 / (i * i + i);
    	ret += term;
    }
    
    return ret;
}

이분 탐색 또한 충분히 오차가 작아질 때까지 반복해야 합니다.

 

Decimal의 경우, C/C++에서는 Decimal에 해당하는 타입이 따로 없습니다.

그래서 전 처음에 그러한 클래스를 새로 정의해야겠다 싶어서 github을 참고하면서 짜봤는데

코드량도 너무 방대하고, 원하는 정밀도까지 높이려니 연산 시간이 너무 오래 걸려서 포기했었습니다.

 

2024.05.06 추가) 백준에서 boost 라이브러리 사용이 이제 불가능합니다.

 

그런데 알아보니 백준에서는 boost 라이브러리를 쓸 수 있었습니다. 괜한 헛고생을 했어요.

multiprecision에서 number<cpp_dec_float<prec>> 타입을 사용하면,

소수점 아래 prec 자리까지 계산할 수 있는 실수형 타입을 사용할 수 있습니다.

예를 들어 50자리의 경우,

typedef number<cpp_dec_float<50>> cpp_dec_float_50;

와 같은 방식으로 사용하면 됩니다.

 

3. 코드

...는 C++로는 제가 직접 푼 게 아닌 셈이니 올리지 않겠습니다.

다만 풀이를 보면 코드는 작성할 수 있습니다.