문제 출처
https://www.acmicpc.net/problem/2869
내 답안
1. 첫번째 답안
A, B, V = map(int, input().strip().split(' '))
L = 0
day = 0
while L <= V:
day = day + 1
L = L + A
if L >= V:
break
L = L - B
print(day)2. 두번째 답안
import math
a, b, v = map(int, input().split())
print(math.ceil((v-a)/(a-b)+1)) #올림함수 사용
풀이 정리
1번 풀이
이것을 생각했던 과정들을 먼저 정리해보려고한다.
간단하여 순서대로 차근차근 해보았다.
1. while문의 조건은 달팽이가 오른 길이인 L이 최종길이와 같은지 확인 후
날짜를 하루씩 더해준다.
2. 낮에 오른 길이인 L을 다시 나무가지길이와 조건과 검증해서 break문을 걸어준다. 조건에 해당하지 않으면 밤에 미끄러지는 길이는 빼준다.
3. 위에 로직을 반복한다.
2번 풀이
첫번째 로직을 돌려보니, 시간초과가 났다.ㅠㅠ 이런문제는 역시 수학적으로 정리해서 코드를 작성하는 것이 더 빠르고 간결한 코드가 작성되는 것임을 깨달았다.
수학적으로 어떻게 공식화를 할수있을까를 가장먼저 고민해보았다.
a(낮에올라가는높이) , b(밤에 미끄러지는 높이) , v(올라가야되는 높이),cnt(마지막날을 제외한 올라간 횟수) 를 놓고 식을 짜보겠다.
v <= ((a-b) x count)) + a 이다. 즉 무엇이냐면 v(올라가야되는 높이) 보다 ((a-b):하루에 올라갈 수 있는 높이) * (마지막날을 제외한 횟수)에 마지막날 a만큼 오르는 것을 더해준 값이 더 커야 한다는 거다.
이를 식을 이항 정리를 하면 (v-a)/(a-b) <= count 가 나온다. 즉, (마지막날을 제외한 횟수는) (v-a)/(a-b) 보다 같거나 커야한다는 말이다.
그럼 여기서 마지막날까지 횟수를 포함시키기 위해선 (v-a)/(a-b) + 1 만 해주면 된다.
정리하면 (v-a)/(a-b) +1<= count +1 (count+1은 마지막날까지 포함한횟수) 이다.
이를 다시 result(==count+1)로 정리해보면 (v-a)/(a-b) +1<= result 로 정리할 수 있다. 결국 이 result 값(출력할 총 횟수)이 (v-a)/(a-b) +1 보다 크면 된다는 것이다.
하지만 여기서 한가지 더 생각해야 할 점이 있다. 만약에 (v-a)/(a-b) + 1 이 1.25 , 2.5 와 같이 소수점으로 나오면 어떻게 해야하는가? 그러면 정답이 result값(총 횟수)은 2번하고 0.5번만 수행하면 되는건가? 이것은 아니다. 횟수라는 건 자연수 이기 때문에 즉 1.25는 2번, 2.5는 3번 이기때문에 result값을 구하기 위해서는 (v-a)/(a-b) + 1 값에 올림함수를 써줘야한다.
따라서 답은 다음과 같다.!
