백준 14786번: Ax+Bsin(x)=C ② (파이썬, 이분탐색)

이번 주에는 이분탐색을 공부 하고있었고, 이분탐색으로 푼 문제중 난도가 가장 높았던 문제였다.

 

다항함수와 삼각함수의 합으로 이루어진 그래프와 상수와의 교점을 구하는 문제이기에 답이 정수로 떨어지지 않고, 오차를 허용하는 형태의 처음보는 문제였다.

 

구간을 정한후 이분탐색을 해야 할것 같았는데 구간을 어떻게 정할지를 구하기 위해서 그래프부터 살펴보았다.

구간을 최대한 좁게 잡아야 탐색시간을 줄일 수 있다고 생각했기 때문이다.

 

처음에는 탐색구간을 정하기 위해 함수의 최대값을 가지는 지점을 구하려 하였으나 y =x는 x가 무한대일때 발산하고, y=sinx는 진동하므로 x+sinx는 발산한다. 따라서 구간설정에 극대점, 최댓값등은 구간설정에 이용할 수 없을것 같았다.

 

다음으로 함수의 그래프를 그려보면서 A,B,C 값의 변화에 따른 근의 구간변화를 살펴보았다.  

A값의 변화에 따른 Ax + Bsinx - C = 0의 해의 변화

y = Ax + Bsinx -C 함수에서 A값이 커질수록 기울기가 커져 y=0과의 교점이 원점과 점점 가까워지는 것을 볼 수 있었다. B값도 마찬가지 였다. 

C값의 변화에 따른 Ax + Bsinx - C = 0의 해의 변화

그러나 C값에 따라서는 C값이 커짐에 따라 0 = Ax + Bsinx - C의 해도 커져서 탐색구간을 잡을때 C값을 신경써야 한다고 생각했다. 따라서 x+sinx = 1의 해는 0보다 크고 Ax + Bsinx - C의 해는 2*C보다 작으므로 탐색구간을 [0,2* C]로 잡았다.

 

처음풀이는 이분탐색의 정석구현대로 풀려 했으나 ( while문의 종료조건을 start <= end로 두고, 그 구간에서 계산한 값과 기준값을 비교하여 구간을 줄여가는 코드) 오차 10^-9와 비교할 대상을 찾지 못하여 풀이를 틀었다.

 

import sys
from math import sin, copysign

A, B, C = list(map(int, sys.stdin.readline().split()))
sign = lambda x: copysign(1, x)


def f(x):
    return A*x + B*sin(x) - C


tol = 10**(-9)
start, end = 0, 2*C

while abs(start-end) > tol:
    mid = (start+end) / 2
    if sign(f(start)) != sign(f(mid)):
        end = mid
    elif sign(f(end)) != sign(f(mid)):
        start = mid

print(mid)

바로 시간초과가 났다. while문의 종료조건을 두구간의 차의 절댓값이 오차보다 작을때로 설정하여 정답은 맞게 나왔지만 4번의 시도동안 모두 시간초과가 났다.

시간초과를 수정하기 위해 구간도 타이트하게 잡아보고, 초기에는 if문의 조건으로 f(start)*f(end) < 0으로 하였으나 10만대의 숫자들 연산에 시간이 많이 쓰이나 싶어 부호를 계산하는 함수를 만들어 조건들을 바꿔가도 계속해서 시간초과가 났다. (96퍼에서 못올라감)

 

따라서 그래프를 보면서 다른 풀이를 생각해냈다.

import sys
from math import sin, copysign

A, B, C = list(map(int, sys.stdin.readline().split()))
sign = lambda x: copysign(1, x)


def f(x):
    return A*x + B*sin(x) - C


tol = 10**(-9)
start, end = 0, 2*C

while abs(start-end) > tol:
    mid = (start+end) / 2
    if f(mid) <= 0:
        start = mid
    else:
        end = mid

print(mid)

알고리즘에 집중하여 수학적 풀이를 놓쳤는데 구간을 무조건 해가 있는 구간으로 잡았고 f(0) = -C (0<C<=10^5)이므로 f(start)는 무조건 음수이므로 f(start)의 부호를 판별할 필요가 없다는 것이였다. 그 부분을 수정하니 72ms로 바로 맞았다. 

 

또한 이분탐색 구간에 대해서도 다시 생각하게 되었는데, 궁금해서 end = 10^5로 두고 제출해봤는데 시간차이 없이 맞았다. 이분탐색 속도에 있어서 구간의 크기는 크게 중요하지 않나보다.

구간길이에 따른 이분탐색 알고리즘의 속도 차이(위: 구간길이 2C, 아래: 구간길이 10^5)