[백준] 2869 달팽이는 올라가고 싶다 python 알고리즘 문제

문제 2869. 달팽이는 올라가고 싶다.

1. 나의 코드와 발상 과정

### 시간초과
a, b, v = map(int, input().split())
day = v // (a - b) + 1   
len_sum = 0
for i in range(1, day):
    len_sum += a
    if len_sum >= v:
        print(i)
        break
    else :
        len_sum -= b
        
        
#####

a, b, v = map(int, input().split())
day = (v - b) // (a - b)
if (v - b) % (a - b) == 0:
    print(day)
else:
    print(day + 1)

0.15초라는 시간제한이 있기 때문에 최소한의 반복을 해야 한다.

반복문을 쓰지 않고 풀어보았다. (위에껀 써봤더니 당연히 시간초과)

 

일수를 구해야 하는데, 단순히 생각해보면 v // a-b 가 아닐까 했다.

 

단순히 v를 a-b로만 나누어 떨어지는 경우와 나누어 떨어지지 않는 경우 두 가지를 생각해볼 수 있다.

나누어 떨어지는 경우는 

v = 5, a = 2, b = 1이라 할 수 있는데,

이 경우 달팽이는 4일이면 도착하지만, v에서 a-b를 나누면 5일이 된다.

 

나누어 떨어지지 않는 경우는

v = 6, a = 5, b = 1 인데,

이 경우 달팽이는 2일이면 도착하지만, v에서 a-b를 나눌 경우, 1.5가 나오게 된다.

 

뭔가 이상했다. 그래서 v를 바로 나누는 것은 아닌 것 같았다.

 

정상을 찍기 전 마지막 날(통과하는 날이 아니라)의 날짜 수를 센다면?

이라는 생각이 들어 마지막 날 미끄러질 것을 대비하여 v-b를 a-b로 나누어준다(몫을 구한다).

그런 다음 나누어 떨어지는 경우는 나머지가 없는 경우를 if문으로 골라내어 그대로 출력해주면 되고,

아닌 경우는 +1 하여 출력하면 된다.

 

2. 고수님의 깔끔한 코딩

a, b, v = map(int, input().split())
print((v - a - 1) // (a - b) + 2)

???

수학적인 문제라서 숏코딩을 봐도 이해가 될 것이라고 생각했지만,

전혀 되지 않았다....

 

 

 

3. 아쉬운 점

굳은 나의 수학적 사고력