[백준 파이썬 2869번]달팽이는 올라가고 싶다 ★올림함수를 활용하고 알고리즘 차근차근 분석하기★등차수열과 범위확인★VER2.0

2869번 문제

VERSION 2.0

 

import sys

#A = list(map(int, sys.stdin.readline().rstrip().split()))
#print(A)

# a = A[0]
# b = A[1]
# V = A[2]
# for i in range(3):
A = list(map(int, sys.stdin.readline().rstrip().split()))
a = A[0]
b = A[1]
V = A[2]
def func(k , a, b):
    res = (a-b)*k + b
    return res
k = (V-b)//(a-b)
if func(k ,a ,b) < V < func(k+1, a, b):
    print(k+1)

elif func(k,a,b) == V:
    print(k)

낮에 올라간 값들이 수열을 이룬다. 따라서 이를 분석해보자

 

 

VERSION 1.0

import sys
import math

A = list(map(int,sys.stdin.readline().split()))

#2 1 5 ==> 5//(2-1) = 5 if (2-1)*(5-2) + 2 >= 5 ==> 5-1 = 4 출력
#5 1 6 ==> 6//(5-1) ==>올림(2) if (5-1)*(2-2) + 5 >= 6 ==> +1 
# ==> (5-1)*(2-1) +5 >=6 ==> +1 ==> 2출력 
#2 -1 2 -1 2 -1 2
firstday = 0
a =2
#firstday = math.ceil((A[2]/(A[0]-A[1])))
#5 1 6 
#6/(5-1) = 1.5 ==> firstday = 2 
# 0 + 5 >=6 x ==> 2출력
#100 99 1000000000
#1000000000/1 = 1000000000
#1*999999998 + 100 > 1000000000
#1*999999900 + 100 > 1000000000
#500 450 5000 ==> firstday = 100 98*50=4900 95*50 = 4750 90*50= 4500
# 5000/ 500 = 9 100-(9+1) 90*50 = 4500 91*500
#500 450 5100 ==> 10.2 50*10 =5000 4500 5000 5500 
#5 1 6 ==>6/4=2 4*(2-3) + 5
#50* 100-(a=10) +500>=A[2]
#500 470 5000 ==> firstday = (5000-500)/30 =150 ==> 167 second =5000/500 = 10 167-10=157
#2 1 5 ==> firstday = 5/1 = 5 // A[2]=5 -2 
#1*3 + 2>=5
firstday = 0
a =2
firstday = math.ceil((A[2]-A[0])/(A[0]-A[1]))
# 2 1 5 firstday = (5-2)/1 = 3
#5 1 6 firstday = (6-5)/4 = 0.25 ==> 1 ===>하루+낮 ==>2일 
if ((A[0]-A[1]) *(firstday) + A[0])>=A[2] : #(하루치올라간 높이) * (꽉채운 일 수) + 낮에 올라가기 >= 전체 높이  
    #1*3 +2 >= 5 
    print(firstday+1) #낮에 올라간거 포함시켜야하므로 하루 더한다.
else: 
    #5 1 6 firstday = (6-5)/1 = 1
    #4*1 + 5>=1
    print(firstday) #

    #100 99 1000000000
    #

깔끔히 정리한 코드

======================================================================

import sys
import math

A = list(map(int,sys.stdin.readline().split()))
firstday = 0
firstday = math.ceil((A[2]-A[0])/(A[0]-A[1]))
if ((A[0]-A[1]) *(firstday) + A[0])>=A[2] : 
    print(firstday+1) 
else: 
    print(firstday)

 

달팽이 결과값

달팽이 문제 파악 알고리즘 순서 : 

 

1.  V미터인 나무 막대 , 낮엔 A미터 올라가고 /// 밤엔 B미터 미끄러진다. 정상에 올라간 후에는 미끄러지지 않는다.

2. 낮에 A미터 올라갈려는 경우 V미터에 도달했을때 멈추게 된다.

3. ==>4번째줄 : A리스트에 A[0] = A미터 올라가기 A[1] = B미터 미끄러지기 A[2] = V미터인 나무 막대

         5번째줄 : firstday = 0 => 며칠걸리는지의 변수 선언

         6번째줄 : (V미터 나무막대 - A미터 올라가기)/(A미터 올라가기 - B미터 미끄러지기) 의 올림 값(math.ceil())

                     ==> 소요일을 파악할 수 있다.

                     

          7번째줄~8번째줄 : (A미터 올라가기 - B미터 미끄러지기)*(소요일) + A미터올라가기 >= V미터

                                   print(소요일 +1)

                                  EX) V=6 A=2 B=1  ==> (6-2)/ 1 = 4

                                       (2-1) * 4 + 2 >= 6

                                       firstday = 4 +1  

                                       print(5)

                                  EX_2) V = 6 A=5 B=1 ==> (6-5)/4 = 0.25 ==> 1

                                          (5-1)*1 +5 >=6

                                          firstday = 1 + 1

                                          print(2)

                                  EX_3)V=1000000000 A =100 B=99 ==> (1000000000-100)/1 = 999999900

                                         (100-99)*999999900 + 100 >= 1000000000

                                         firstday = 999999900+1

          9번째줄~10번째줄

 ★★★KEY POINT★★★

1. (V미터 나무막대 - A미터 올라가기)/(A미터 올라가기 - B미터 미끄러지기) 의 올림 값

==> 소요일(다음날의 A미터 올라가기 전의)

2. (A미터 올라가기 - B미터 미끄러지기)*(소요일) + A미터올라가기 >= V미터

    ==>소요일 만큼 올라간후 그다음날의 A미터 올라갔을때 V미터에 도달 혹은 그 이상이라면 소요일+1값을 취해준다.