https://www.acmicpc.net/problem/13705
13705번: Ax+Bsin(x)=C
첫째 줄에 정수 A, B, C가 주어진다. (0 < B ≤ A ≤ 100,000, 0 < C ≤ 100,000)
www.acmicpc.net
엄청나게 높은 정밀도를 요구하는 문제.
파이썬의 Decimal 모듈을 사용해서 풀었다.
f(x) = Ax + Bsin(x) 일때
f'(x) = A + Bcos(x) 이고 A>=B 이므로 f'(x) 는 모든 x에 대하여 0 이상임을 확인할 수 있다.
f(x)가 증가하는 함수이기 때문에, 이분탐색을 통해서 답을 구해줄 수 있고,
이렇게 해결할시 보다 쉬운 버전인 14786번을 해결할 수 있다.
웃긴게 요구하는 정확도 자체는 14786이 더 높다;;;
테스트케이스의 강함 / 약함 정도의 차이인거같은데 겉모습만 보고 지레짐작하지 말도록 하자
나는 일반적인 비교조건과 다르게 정확도를 많이 높이고 이분탐색의 종료조건을 K번 돌림으로 정해서
무한루프에 들어갈 일이 없게 하였다.
이분탐색 범위도 상당히 러프하게 그냥 커버할수있는 넓은 범위로 했던것 같다.
어차피 한번 돌릴때마다 범위가 절반으로 줄어들기 때문에 파이썬이라는 언어 특성상 숫자는 널널히 잡아도
크게 상관이 없을듯?
언어에 내장된 math.sin() 함수보다 더 높은 정확도의 연산을 요구하고 있기 때문에
sin함수를 직접 구해줘야 할 필요성이 있다.
sin함수를 직접 구하는 과정에는 테일러 급수가 이용된다고 하는데
난 대학수학 책도 펼쳐보지 못한 고딩이기 때문에
Decimal 라이브러리 문서에 있는 sin함수의 구현을 가져와서 사용했다.
https://python.flowdas.com/library/decimal.html
decimal --- 십진 고정 소수점 및 부동 소수점 산술 — 파이썬 설명서 주석판
decimal 모듈은 빠르고 정확하게 자리 올림 하는 십진 부동 소수 산술을 지원합니다. float 데이터형보다 다음과 같은 몇 가지 장점을 제공합니다: 모듈 설계의 중심 개념은 세 가지입니다: 십진수,
python.flowdas.com
참고하도록 하자
복붙방지를 위해서 다이아 문제인 본 문제는 소스코드를 공개하지 않도록 하겠다
제출언어 기본을 c++으로 해놔서
절반이 컴파일에러다 ㅋㅋㅋㅋ
pypy3으로 제출했을때 TLE를 받았었으니 참고해서 제출하도록 하자.