백준 2869번 파이썬 풀이: 달팽이는 올라가고 싶다

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

 

알고리즘 분류: 수학

 

링크: https://www.acmicpc.net/problem/2869

 

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

 

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

 

 

 

문제 파악

 

굉장히 쉬운 문제라고 생각했다가 시간 초과가 나오기 쉬운 문제이다.

 

정답 비율이 낮은 이유도 시간 초과에 걸린 사람들이 많은 것으로 추측된다.

 

이 문제의 핵심은 정상에 올라간 후에는 밤에 미끄러지지 않는다는 것이다.

 

따라서 단순 계산을 잘못하면 정상까지 올라갔다가 밤에 다시 미끄러진 후 다음날 올라가는 경우를

 

계산해버리는 불상사가 일어나기도 한다.

 

 

코드

 

먼저 정답 코드를 보기 전에 어떤식으로 풀어서 틀렸었는지를 보자면

 

처음 문제를 풀었을 때는 이렇게 풀어서 틀렸었다.

 

틀린 이유는 당연히 시간초과이다.

 

이런식으로 1씩 늘려가다 보면 a = 2, b = 1, v = 1,000,000,000 이라고 주어졌을 때

 

굉장히 많은 시간이 소요될 것이 뻔하다.

 

그렇다면 반복문을 돌지 않고 한번에 값을 계산해야 된다는 소리인데

 

정답 코드를 보자면

 

day = (v - b) / (a - b) 라고 표현했는데 이는 정상에 한번 도달하면 밤에 미끄러지지

 

않는 것을 고려해 준것이다.

 

그냥 day = v / (a - b) 라고 해버리면 앞서 말한듯이 정상에 올라갔어도 밤에 내려와서

 

다음날 다시 올라가는 불상사가 생길 수 있다.

 

혹시라도 시간초과에 걸릴까봐 input()도 sys.stdin.readline()으로 바꿔주었다.

 

day = (v - b) / (a - b) 로 표현하면 당연히 정수로 딱 안떨어지고 소수로 나오는 경우가

 

생기는데 이를 math 모듈을 사용해서 올림 처리를 해주었다.

 

4.0 은 4일이 걸린다는 것이지만 4.2는 5일이 걸리는 것이기 때문이다.