[Python] 백준 2869 (달팽이는 올라가고 싶다)

*문제에 대한 내 생각

 만일 시간제한이 없었다면 파이썬 자습서에나 나오는 예제였을 것이다.

 문제자체가 어렵지는 않지만 실수할 것들이 많아 나도 4번의 시도끝에 성공했다.

 

 

*문제 풀이

-아이디어

 가장 처음 이 문제를 마주쳤을 때 나오는 실수는 올라가는 거리와 내려오는 거리의 차를,

 높이에 나누어 그 몫에 1을 더하는 경우다.(즉 V//(A-B) + 1)

 그러나 이 경우는 중대한 문제가 있다. 아침에 올라가는데 성공하는 경우를 제외한 것이다.

 만일 3M를 올라가고 1M를 내려온다면, 높이가 4일때 위의 식으로는 3이 나온다.

 그러나 실제로는 2가 답이다. 다시말해 위의 식은 아침에 막대기를 다 올랐음에도,

 다시 밤에 내려갔다가 다음날 다시 올라오는 구조다.

 

 하지만 이러한 실수를 하는 경우는 거의 없을 것이다.

 나 역시 그렇듯, 대부분이 막혔던 난관은 시간초과라 생각한다.

 내가 처음 만든 코드는 아래와 같다.

a,b,v = map(int,input().split())
k = 0	#올라가는 데 걸리는 일수
d = 0	#올라간 높이
while 1:
    k+=1
    if a*k-b*(k-1)>=v:
        break
print(k)

 하지만 이와같은 코드는 부등식의 계산이 이루어지기 때문에 시간초과가 생긴다.

 따라서 A,B,V가 입력되면 바로 답이 나오는 구조여야 한다.

 무슨말이냐 하면, 위와 같은 코드는 K의 값을 점차 늘리기 때문에 결과적으로 K의 값만큼 while문을 반복한다.

 하지만 if구문의 조건식,

 a*k-b*(k-1) => v 를 이항시켜 정리하면 k>=(v-b)/(a-b)로 바꿀 수 있다. 이를 통해 k의 값을 바로 도출 할 수 있다.

 

 

-코드

 우리는 k,즉 일수를 최소화시켜야 한다. 따라서 k는 (v-b)/(a-b) 혹은 (v-b)//(a-b)+1이다.

 답이 두개인 경우는 (v-b)/(a-b)가 분수인 경우가 있기 때문이다.

 예를 들어 (v-b)/(a-b)가 4.0인 경우 k는 4이지만, (v-b)/(a-b)가 4.1인 경우 k는 5이다(k는 '일수'다. 즉 4.1일은 없다).

 따라서 k=(v-b)/(a-b)로 두고, int(k)와 k가 같다면 k는 (v-b)/(a-b), 다르다면 k는 (v-b)/(a-b)+1이다.

 

 

a,b,v = map(int,input().split())
k = (v-b)/(a-b)
print(int(k) if k == int(k) else int(k)+1)	#삼항연산자

 

 

 

*결과

 91바이트에 56ms이 나왔다.

 이보다 짧은 시간은 아직까지 없다.

 나보다 짧은 사람들의 코드를 보면 (V-A-1)//(A-B) +2와 같이 작성했는데, 이 이유는 아직 모르겠다.