/<> 백준 13705: Ax+Bsin(x)=C - C#

/<> 백준 13705: Ax+Bsin(x)=C

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

solved.ac

• Diamond IV

문제

A, B, C가 주어졌을 때, Ax+Bsin(x)=C를 만족하는 x를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 정수 A, B, C가 주어진다. (0 < B ≤ A ≤ 100,000, 0 < C ≤ 100,000)

출력

첫째 줄에 x를 반올림해서 소수점 여섯째 자리까지 출력한다.

예제 입력 1

1 1 20

예제 출력 1

19.441787

코드 (채점번호 31438269, 31399971)

https://www.acmicpc.net/source/31438269
https://www.acmicpc.net/source/31399971

<공통 부분>

using System;

decimal piD = decimal.Parse("3.14159265358979323846264338327950288419716939937510");
decimal piD2 = piD / 2;
decimal piD4 = piD / 4;

decimal[] sinDenominators = new decimal[30];
decimal[] cosDenominators = new decimal[30];

for (int i = 1; i <= 30; i++)
{
    sinDenominators[i - 1] = 2 * i * (2 * i + 1);
    cosDenominators[i - 1] = (2 * i - 1) * 2 * i;
}

decimal Sin(decimal x)
{
    if (x == 0)
        return decimal.Zero;
	
    if (x < 0)
        return -Sin(-x);
	
    if (x > piD)
    {
        if ((int)decimal.Floor(x / piD) % 2 == 0)
            return Sin(x % piD);
        else
            return -Sin(x % piD);
    }
	
    if (x > piD4)
        return Cos(piD2 - x);

    decimal x2 = x * x;
	
    decimal result = 1;
	
    for (int i = 29; i >= 0; i--)
    {
        result = x2 / sinDenominators[i] * result;
        result += i % 2 == 0 ? 1 : -1;
    }

    return x * result;
}

decimal Cos(decimal x)
{
    if (x == 0)
        return decimal.One;
	
    if (x < 0)
        return Cos(-x);
	
    if (x > piD)
    {
        if ((int)decimal.Floor(x / piD) % 2 == 0)
            return Cos(x % piD);
        else
            return -Cos(x % piD);
    }
	
    if (x > piD4)
        return Sin(piD2 - x);

    decimal x2 = x * x;
	
    decimal result = 1;
	
    for (int i = 29; i >= 0; i--)
    {
        result = x2 / cosDenominators[i] * result;
        result += i % 2 == 0 ? 1 : -1;
    }

    return result;
}

string[] input = Console.ReadLine().Split(' ');

decimal a = decimal.Parse(input[0]);
decimal b = decimal.Parse(input[1]);
decimal c = decimal.Parse(input[2]);

<31438269번 (이분법 사용)>

decimal Calc(decimal x) => a * x + b * Sin(x) - c;

decimal left = (c - b) / a - decimal.One;
decimal right = (b + c) / a + decimal.One;
decimal middle;

do
{
    middle = (left + right) / 2;
	
    decimal result = Calc(middle);
	
    if (result < 0)
        left = middle;
    else if (result > 0)
        right = middle;
    else
        break;
} while (right - left >= decimal.Parse("0.000000000000000000001"));

Console.WriteLine(decimal.Round(middle, 6, MidpointRounding.AwayFromZero));

<31399971번 (뉴턴-랩슨 방법 사용)>

decimal result = c / a;
decimal beforeResult;

do
{
    beforeResult = result;
	
    decimal sinx = Sin(result);
    decimal cosx = Cos(result);
	
    result = (c + b * result * cosx - b * sinx) / (a + b * cosx);
} while (Decimal.Round(result, 12) != Decimal.Round(beforeResult, 12));

Console.WriteLine(Decimal.Round(result, 6, MidpointRounding.AwayFromZero));

설명

이 문제는 실수오차를 최대한 줄여야 하는 문제이다.
따라서 이번 문제에서는 128비트 부동 소수점 타입인 decimal타입을 사용하였다.
그런데, C#에서는 decimal타입을 리턴하는 Sin(), Cos() 메소드를 제공해주지 않는다.
따라서 이 메소드들을 구현 해 준다.

먼저, decimal타입 $\pi$값도 기본적으로 제공해 주지 않으므로, 추가적으로 정의 해 준다.

decimal piD = decimal.Parse("3.14159265358979323846264338327950288419716939937510");
decimal piD2 = piD / 2;
decimal piD4 = piD / 4;

그 다음, 테일러 급수를 이용한 decimal타입 Sin()메소드와 Cos()메소드를 구현 해 준다.

decimal[] sinDenominators = new decimal[30];
decimal[] cosDenominators = new decimal[30];

for (int i = 1; i <= 30; i++)
{
    sinDenominators[i - 1] = 2 * i * (2 * i + 1);
    cosDenominators[i - 1] = (2 * i - 1) * 2 * i;
}

decimal Sin(decimal x)
{
    if (x == 0)
        return decimal.Zero;
	
    if (x < 0)
        return -Sin(-x);
	
    if (x > piD)
    {
        if ((int)decimal.Floor(x / piD) % 2 == 0)
            return Sin(x % piD);
        else
            return -Sin(x % piD);
    }
	
    if (x > piD4)
        return Cos(piD2 - x);

    decimal x2 = x * x;
	
    decimal result = 1;
	
    for (int i = 29; i >= 0; i--)
    {
        result = x2 / sinDenominators[i] * result;
        result += i % 2 == 0 ? 1 : -1;
    }

    return x * result;
}

decimal Cos(decimal x)
{
    if (x == 0)
        return decimal.One;
	
    if (x < 0)
        return Cos(-x);
	
    if (x > piD)
    {
        if ((int)decimal.Floor(x / piD) % 2 == 0)
            return Cos(x % piD);
        else
            return -Cos(x % piD);
    }
	
    if (x > piD4)
        return Sin(piD2 - x);

    decimal x2 = x * x;
	
    decimal result = 1;
	
    for (int i = 29; i >= 0; i--)
    {
        result = x2 / cosDenominators[i] * result;
        result += i % 2 == 0 ? 1 : -1;
    }

    return result;
}

테일러 급수는 넉넉하게 30항 정도면 되는 것 같다.

위 메소드들을 사용하여, 오차가 일정 이하가 될 때 까지, 이분법 혹은 뉴턴-랩슨 방법 중 아무거나 사용하여 계산하면 통과한다.