특별한 이분탐색 -실수 구간에서도 이분탐색이 가능할까-

1. 문제

 

14609번: 구분구적법 (Large) (acmicpc.net)

14609번: 구분구적법 (Large)

 

2. 풀이

 

실제 적분값과 근삿값이 일치하게 만드는 epslion을 찾는다

 

그러면 실제 적분값을 먼저 구해야겠지

 

최대 10차 다항함수까지로 제한되어있고 다항함수 적분 방법도 힌트로 나와있다

 

 

그러면 $c_{0}x^{k} + c_{1}x^{k-1} + ... + c_{k}$를 적분하면 된다

 

그러면 $$\frac{c_{0}x^{k+1}}{k+1} + \frac{c_{1}x^{k}}{k} + ... + c_{k}x+C$$

 

a부터 b까지 적분한다고 하면...

 

$$(\frac{c_{0}b^{k+1}}{k+1} + \frac{c_{1}b^{k}}{k} + ... + c_{k}b) - (\frac{c_{0}a^{k+1}}{k+1} + \frac{c_{1}a^{k}}{k} + ... + c_{k}a)$$

 

얘를 코드로 나타내면 되겠지

 

for문을 이용한 누적합으로 쉽게 할수 있을 것 같다

 

k = int(stdin.readline())

c = list(map(int,stdin.readline().split()))

a,b,n = map(int,stdin.readline().split())

real = 0

for i in range(k+1):
    
    real += c[i]*(((b**(k+1-i))- (a**(k+1-i)))/(k+1-i))

 

다음 근삿값을 구해야하는데..

 

 

후자의 식을 구해야한다.

 

그런데 epslion이 임의의 값이고, 특정한 값일때 두 식이 일치하는지 구하고 싶다.

 

epslion이 0부터 $\Delta{x}$까지 임의의 값이니까.. 어렵게 생각하지 말고 0을 start, $\Delta{x}$를 end로 한 다음에,

 

이분탐색으로 mid를 esplion값으로 지정한 다음에, 근삿값을 계산해서 real과 차이가 나는지 조사해보면 될 것 같다

 

여기서 주의할 점?은 mid를 구할때 start + (end - start)//2로 습관처럼 정수 나눗셈을 하면 안된다는거..

 

실수니까 실수나눗셈 start + (end - start)/2로 해야한다는거 

 

def binary_search(a,b,n,real,k,c):
    
    delta = (b-a)/n

    start = 0
    end = delta

    while 1:
        
        approx = n*(c[-1])
        
        mid = start + (end - start)/2

        for j in range(1,k+1):
            
            for h in range(n):
            
                approx += (c[-(j+1)]*((a+h*delta+mid)**j))
        
        approx *= delta

 

그러면 일단 비교를 어떻게 해야할까?

 

실제값 real이 근삿값 approx보다 크다면?

 

그러면 현재 mid가 실제값 real에 일치시키기에는 작다는 뜻이므로, start를 mid보다 큰 쪽으로 옮겨서 mid이후를 탐색해야한다

 

실제값 real이 근삿값 approx보다 작거나 같다면?

 

현재 mid가 실제값 real과 일치시키기에 충분하므로, mid 이전을 탐색해서 그 차이를 더욱 줄여야한다

 

        if real > approx:

            start = mid + 1

        else:

            end = mid

 

 

근데 이렇게 하면...당연히 안되겠지

 

현재 탐색 구간이 무수히 많은 실수구간이라 정수구간처럼 단위 길이가 1이 아니다

 

그러면 0에 가까운 아주 적은 값을 선택해야한다는 뜻인데..

 

문제가 실제값과 근삿값의 차이가 10^(-4) 이내면 정답이라고 했으므로, 이 정도를 선택하면 될 것같다

 

from sys import stdin

def binary_search(a,b,n,real,k,c):
    
    delta = (b-a)/n

    start = 0
    end = delta

    while 1:
        
        approx = n*(c[-1])
        
        mid = start + (end - start)/2

        for j in range(1,k+1):
            
            for h in range(n):
            
                approx += (c[-(j+1)]*((a+h*delta+mid)**j))
        
        approx *= delta
            
        if real > approx:

            start = mid + 10**(-5)

        else:

            end = mid

    return end

 

다음으로 언제까지 탐색을 해야하는가?

 

start < end를 만족하는 경우에 탐색을 해야하는가?

 

start,end가 실수이다 보니 아주 적은 차이가 나더라도 이분탐색을 계속 수행하면서.. 무한 루프에 빠지더라

 

 

그래서 start와 end의 차이가 적절한 값 이내라면, 탐색을 중단하도록 만들어야 겠다

 

역시 실제값과 근삿값의 차이가 10^(-4) 이내면 정답이라고 하니, 이 정도 값을 선택하면 될 것 같다

 

from sys import stdin

def binary_search(a,b,n,real,k,c):
    
    delta = (b-a)/n

    start = 0
    end = delta

    while abs(start-end) > 10**(-5):
        
        approx = n*(c[-1])
        
        mid = start + (end - start)/2

        for j in range(1,k+1):
            
            for h in range(n):
            
                approx += (c[-(j+1)]*((a+h*delta+mid)**j))
        
        approx *= delta
            
        if real > approx:

            start = mid + 10**(-5)

        else:

            end = mid

    return end
        
k = int(stdin.readline())

c = list(map(int,stdin.readline().split()))

a,b,n = map(int,stdin.readline().split())

real = 0

for i in range(k+1):
    
    real += c[i]*(((b**(k+1-i))- (a**(k+1-i)))/(k+1-i))

print(binary_search(a,b,n,real,k,c))

 

 

참고로 이 문제에서 요구하는 epsilon이 없다면, -1을 출력하라고 하는데.. 불가능한 epsilon이 없는 경우는 존재하지 않는다

 

다항함수의 계수가 모두 0 이상이므로, 적분 근삿값은 반드시 증가함수이다.

 

따라서 "epsilon이 0일때의 최소 근삿값 <= 실제 적분값 <= epsilon이 $\Delta{x}$일때 최대 근삿값"이 반드시 성립한다.

 

그러므로 중간값 정리에 의해 실제 적분값과 일치하게 되는 epsilon이 반드시 존재한다

 

---------------------------------------------------------------------------------------------------------------------------

 

**중간값 정리

 

함수 f(x)가 [a,b]에서 연속이며, f(a)와 f(b)가 같지 않을때, f(a)와 f(b) 사이 임의의 k에 대하여, f(c) = k인 c가 (a,b)에 적어도 하나 반드시 존재한다.

 

 

f(x) = 적분 근삿값이고, a가 0, b가 $\Delta{x}$일때, f(a)와 f(b)사이 어떤 값 k = "실제 적분값"에 대하여,

 

어떤 epsilon = c에 대한 근삿값 = f(c) = "실제 적분값"을 만족하는 c가 (0,$\Delta{x}$)에 반드시 존재한다.