[알고리즘] 백준 2869 (파이썬 풀이)

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

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

문제

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

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

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

입력

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

출력

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

 

 

해결코드

실패코드-1

a,b,v = map(int, input().split())
cnt = 0
while(v >= 0):
    v = v-a
    cnt += 1
    if (v==0 or v<=0):
        break
    v = v+b
print(cnt)

굉장히 쉬운문제인줄 알고 접근했다가 계속해서 시간 초과가 나는 문제이다. while문을 돌려서

카운트를 올려주면 되는 문제일줄 알았는데 그렇게되면 카운트 값만큼 반복문을 돌리게 되어 많은 시간이

소요되는 것을 알았다. 애초에 반복문을 쓰면 안되고 값이 카운트 값이 바로 나와야 성공시키는 셈이다.

 

해결코드

import sys
import math

a,b,v = map(int, sys.stdin.readline().split())
cnt = math.ceil((v-b)/(a-b))
print(cnt)

입력 시간을 줄이기 위해 sys라이브러리와 소수점 올림처리를 하기위한 math 라이브러리를 사용하였다.

나무 정상에 올라간 이후에는 떨어지지 않기 때문에 그 부분을 주의해서 식을 작성하면 성공이다.

 

문제풀이

위에 얘기한 이유로 라이브러리 두개를 import해준다.

map함수를 이용하여 a,b,v를 한 줄에(띄어쓰기 구분) 모두 받아준다.

참고로 a=올라간거리 b=떨어진거리 v=나무길이 이다.

cnt는 정상에 도착하기까지 몇 일이나 걸리는지를 나타낸다.

만약 cnt = v/(a-b) 이랬다면 정상에 올라간 이후 떨어지지 않는다는 것을 고려안한 것이다.

값이 소수점으로 나올 수 있으므로(x.x일) math.ceil을 통해 올림처리를 해준다.