[백준] 2869 - 달팽이는 올라가고 싶다.

문제 : www.acmicpc.net/problem/2869

2869번: 달팽이는 올라가고 싶다

 

 

문제 정답률이 약 26%로 낮은 편이다.

 

실수에 주의하며 어떻게 풀지 계획해보자.

 

A = 100, B = 99, V = 200일 때, 하루에 1m씩 올라갈 수 있으므로 200일이 걸린다.

 

라고 하면 틀리게 된다.

 

정상에 올라간 후에는 미끄러지지 않는다고 했으므로, 101일 째 낮에 200m를 모두 올라간 후 이동이 끝난다.

 

이를 수식화해보자.

 

1) A - B = D 라고 하자.
2) ( V - A ) / D 는 ( V - A )미터를 올라가는데 걸리는 시간이다.
3) ( V - A )미터를 올라간 후 다음날 낮에 A미터를 올라가면 된다.
4) 따라서 답은 ( V - A ) / D + 1

 

기본적인 아이디어는 위와 같다.

 

예외적으로 V - A / D 가 정수가 아닌 경우는 그냥 올림해버리면 된다.

 

올림했으므로  V - A / D 일 째에 달팽이는 ( V - A )미터보다 더 위쪽에 있겠지만,

 

V - A + D 보다는 아래쪽에 있다. -A + D = -B < 0 이므로 V - A + D < V 이다.

 

즉 이 경우에도 달팽이는 다음날 아침에 정상에 도착한다.

 

주의: ceil은 올림해주는 함수이므로 정수를 반환한다고 착각하기 쉬운데, 반환형이 double이다.
따라서 명시적으로 int형으로 형변환 해주지 않으면 백준에서 틀렸다고 판단한다.