[기초-시간복잡도] ★백준 2869번 달팽이는 올라가고 싶다 with Python3

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

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

문제

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

내 풀이

import sys
import math
a, b, v = map(int, sys.stdin.readline().split())
c = a-b
s = (v-a)/c
print(math.ceil(s)+1)

해설

처음으로 시간복잡도를 고려한 문제. 무려 시간제한이 0.15초 . 비효율적인 for문은 바로 컷이다. 그다지 정돈 되지못했고 완전히 이해하고 풀이를 성공시키지도 못했다. 하지만 맞았으면 되지.

정답 풀이

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

출처:https://stultus.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-2869-%EB%8B%AC%ED%8C%BD%EC%9D%B4%EB%8A%94-%EC%98%AC%EB%9D%BC%EA%B0%80%EA%B3%A0-%EC%8B%B6%EB%8B%A4

 

해석

 하지만 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이다.

 

if문으로 float형을 처리할수있다는게 대단하다. 나는 그걸 제대로 접근 못해서 math.ceil을 사용했다.