나눗셈 실수오차가 생긴다면 직접 나눗셈을 구현하기

1206번: 사람의 수 (acmicpc.net)

 

 

n명의 사람이 0점부터 10점까지 정수로 존재하는 설문조사 문항에 점수를 내서 각 문항마다 평균을 낸 점수가

 

실수로 주어질때, n이 될 수 있는 가장 작은 정수를 구하는 문제

 

평균이 소수점 셋째자리까지만 주어진다

 

예를 들어 32/106 = 0.3018867924528302... 인데 0.301만 주어지는

 

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

 

만약 설문조사한 사람 수가 x명이고 i번째 문항의 점수 합이 v이면

 

$$\frac{v}{x} \approx A[i]$$

 

A[i]가 소수점 넷째자리에서 버려져있으므로

 

$$A[i] <= \frac{v}{x} < A[i]+0.001$$

 

그러므로 $$A[i]*x <= v  < A[i]*x + 0.001x$$

 

이 범위를 만족하는 정수 v가 있다면 그러한 정수 v는 i번째 문항의 점수 합이 될 수 있다

 

여기서 x는 1부터 1000명까지만 가능하다

 

왜냐하면 소수점 셋째자리까지만 주어지기 때문에 x = 1000이면 점수 합이 무조건 정수이므로 1000명이면 반드시 조건을 만족한다

 

이제 x = 1부터 1000까지에 대하여 가능한 정수 v로부터 v/x가 A[i]와 같은지 조사하면 된다

 

그런데 A[i]는 소수점 셋째자리까지만 나와있고 v/x를 하면 그 이상이 나오니까.. 소수점 셋째자리까지만 적당히 비교하면

 

될 수 있겠지만 부동소수점 오차때문인지 그렇게 하면 틀리는

 

그래서 v/x를 정확하게 소수점 셋째자리까지만 구한다

 

실제 나눗셈 하는 방법대로.. 아래 그림을 직접 구현하는 것이다

 

 

 

 

#a/b를 소수점 셋째자리까지만 정확하게 구하는 나눗셈
def divide(a,b):
    
    answer = []

    p,r = a//b, a%b

    answer.append(str(p))
    answer.append('.')

    a = r*10

    while len(answer) < 5:

        p,r = a//b, a%b
        answer.append(str(p))
        a = r*10
    
    return float(''.join(answer))

 

 

근데 문제는 v를 찾는데 실수오차로 자꾸 틀린다는거

 

x = 1,2,3,...,1000이고 A[i]가 실수인데 하한 A[i] * x로 실수와 정수의 곱으로 실수이고

 

A[i]*x + 0.001 * x가 v의 상한인데 A[i] * x + 0.001*x로 실수의 합을 구해보면...

 

 

 

위와 같이 예상하지 못한 값이 나올 수가 있음

 

예를 들어 131.0이어야하는데 130.9999999999991 이렇게 나올수도 있다는거지

 

그래서 그냥 Decimal로 해결하는게 마음 편하다

 

from sys import stdin
from decimal import Decimal

def divide(a,b):
    
    answer = []

    p,r = a//b, a%b

    answer.append(str(p))
    answer.append('.')

    a = r*10

    while len(answer) < 5:

        p,r = a//b, a%b
        answer.append(str(p))
        a = r*10
    
    return float(''.join(answer))

n = int(stdin.readline())

A = []

for _ in range(n):
    
    s = Decimal(stdin.readline())
    A.append(s)

x = 1

for x in range(1,1001):
    
    no = False

    for i in range(n):
        
        v1 = A[i]*Decimal(x)
        v2 = (A[i] + Decimal('0.001'))*Decimal(x)
        
        if int(v1) == v1:
            
            v1 = int(v1)
        
        else:
            
            v1 = int(v1) + 1
        
        if v1 < v2:

            d = divide(v1,x)
            
            if d != float(A[i]):

                no = True
                break
        
        else:
            
            no = True
            break
    
    if no == False:
        
        break

print(x)

 

 

아니면 생각하기 싫다면 그냥 v = A[i]*x해놓고 int(v), int(v)+1 두가지 조사해보는것도 AC받기는 하는데

 

흠 뭔가 좀 아쉬워

 

n = int(stdin.readline())

A = []

for _ in range(n):
    
    s = float(stdin.readline())
    A.append(s)

x = 1

for x in range(1,1001):
    
    no = False

    for i in range(n):
        
        v = A[i]*x

        v1 = divide(int(v),x)
        v2 = divide(int(v)+1,x)

        if v1 != A[i] and v2 != A[i]:

            no = True
            break
    
    if no == False:
        
        break

print(x)