되도록이면 실수로 알고리즘을 풀지 말아야하는 이유1

1. 문제

 

27496번: 발머의 피크 이론 (acmicpc.net)

27496번: 발머의 피크 이론

 

2. 풀이

 

혈중 알코올 농도는 알코올 양 정수 * 0.001로 정의한다고 하니까,

 

정수 배열로 주어지는 배열을 왼쪽부터 순회하면서, 0.001을 곱한 다음 합해나가면서,

 

매 인덱스마다 0.129와 0.138사이에 몇번이나 있었는지 세면 될것

 

O(N)에 해결하기 위해 prefix sum을 사용한다.

 

그런데 시간 L 이후에는, L 전에 먹었던 알코올이 사라지므로... 

 

최초로 술을 먹은 시간부터 L 이후부터는, 0번 원소부터 빼줘야할 것이다.

 

특히 몇번 원소를 빼줬는지도 변수로 저장해서 기억하고 있어야 할것이다

 

from sys import stdin

n,l = map(int,stdin.readline().split())

A = [a*0.001 for a in map(int,stdin.readline().split())]

answer = 0

if A[0] >= 0.129 and A[0] <= 0.138:
    
    answer += 1

blood = [0]*n

blood[0] = A[0]

t = 0
s = 0

for i in range(n-1):

    blood[i+1] = blood[i]+A[i+1]

    t += 1

    if t >= l:

        blood[i+1] -= A[s]
        s += 1
    
    if blood[i+1] >= 0.129 and blood[i+1] <= 0.138:
        
        answer += 1
        
print(answer)

 

근데 이렇게 내면 오답이더라

 

4 2
200 145 71 58

 

여기서 답이 1인데, 0을 내는 문제

 

왜 그런가 보기 위해 중간에 blood를 print해보니까...

 

 

컴퓨터는 실수 연산에 상당히 취약하다.

 

실수 연산이 누적되는 경우 무시하지 못할 오차가 발생하게 된다.

 

그래서 알고리즘 문제에서 일반적으로 정수를 주로 다루며 실수를 사용한 문제의 경우에 오차가 작으면 정답으로 인정해주는 경우가 많다

 

아무튼 정수만을 사용해서 연산을 할 수 있는 경우나,

 

오차에 상당히 민감한 이런 문제 같은 경우... 즉, 오차를 절대로 허용하지 않는 경우..

 

가능하면 정수만으로 문제를 해결하는게 제일 좋다.

 

이 문제도 사실 정수만으로 해결이 가능하다..

 

어떻게 가능하냐고??

 

a*0.001 + b*0.001 = (a+b)*0.001이잖아..

 

따라서, A 배열을 처음에 0.001 곱해서 변환시키지 말고, 애초에 정수 배열로만 다루고

 

정수 배열에서 누적합을 한 다음에.. 마지막에 부등식에서 0.129이상 0.138이하에 속하는지 검사할때만,

 

0.001 곱해서 비교하면 그만이다

 

from sys import stdin

n,l = map(int,stdin.readline().split())

A = list(map(int,input().split()))

answer = 0

if A[0]*0.001 >= 0.129 and A[0]*0.001 <= 0.138:
    
    answer += 1

blood = [0]*n

blood[0] = A[0]

t = 0
s = 0

for i in range(n-1):

    blood[i+1] = blood[i]+A[i+1]

    t += 1

    if t >= l:

        blood[i+1] -= A[s]
        s += 1
    
    if blood[i+1]*0.001 >= 0.129 and blood[i+1]*0.001 <= 0.138:
        
        answer += 1
        
print(answer)

 

아니 근데.. 여기까지 쓰고 나서 또 든 생각이

 

0.001 곱하는 것도 사실 필요가 없다

 

그냥 정수만으로 다룬다고 한다면.. 129이상 138이하인지 검사하는 것이랑 똑같잖아..

 

from sys import stdin

n,l = map(int,stdin.readline().split())

A = list(map(int,input().split()))

answer = 0

#최초 알코올 섭취후 129이상 138이하인지 검사
if A[0] >= 129 and A[0] <= 138:
    
    answer += 1

blood = [0]*n

#알코올 누적합 배열
blood[0] = A[0]

t = 0 #섭취 몇시간째
s = 0 #몇번 알코올이 빠졌는지,

for i in range(n-1):

    blood[i+1] = blood[i]+A[i+1]

    t += 1
    
    #지속시간 L시간 이후에는, 0번원소부터 알코올이 빠져나감
    if t >= l:

        blood[i+1] -= A[s]
        s += 1
    
    #현재 시점에 129이상, 138이하인지 검사해서 지속시간 갱신
    if blood[i+1] >= 129 and blood[i+1] <= 138:
        
        answer += 1
        
print(answer)