[파이썬] 백준 2869번 달팽이는 올라가고 싶다

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

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

이틀전에도 뭐 안되다고 결국 예제에 있는 건 다 풀리는데 시간초과돼서 나왔는데

오늘 들어가서 그 때보다 더 쉽게 풀어서 올렸더니 또 시간초과 ㅎㅎ

 

이틀 전 코드는 기억안나고

a,b,v=map(int,input().split())
h=0 #height(total)
dh=0 #day height
d=0 #day

while dh<v:
    d=d+1
    dh=h+a
    h=dh-b
print(d)

이 코드 사용했는데 시간초과 뜬다. ㅠ 코드 별로 안써서 통과될 줄 알았는데 역시 iteration 때문인건지 아닌건지... 아무래도 예제 3은 내 방식이면 iteration을 너무 많이하게 돼서 그냥 그 차이로 더하는 iteration을 넣어야 하나보다. 그렇게 해서 다시해보기로 하는 즁..

 

Traceback (most recent call last):
  File "C:/Users/파일이름.py", line 1, in <module>
    a,b,v=map(int,input().split)
TypeError: 'builtin_function_or_method' object is not iterable

처음에 계속 이거 떠서 어디서 잘못됐지 했는데....

응 ^^ map(int, input().split)이 아니라 map(int,input().split())야^^..ㅋㅋ

 

그래서 또 다시 풀었는데

a,b,v=map(int,input().split())
h=0 #height(total)
d=0 #day

while h+b<v:
    d=d+1
    h=h+(a-b)
    
print(d)

이번에도 예제 3 돌릴 때 10초 넘게 나오는 거 보면 그냥 iteration이 아니라 수식으로 풀어야할 것 같다

h+b<v로 한 건 낮 고려하려고 한건데, 이게 맞는지 아닌지는 검증안해보고 그냥 때려넣은 건데 예제 1이랑 2는 문제없긴 했다. 하여튼 이게 맞든 틀리든 시간오바되니까 또 다르게 풀어야함 ㅠㅠ

 

 

그래서 결국 맞췄다~~예

a,b,v=map(int,input().split())
day=(v-b)//(a-b)
if (v-b)%(a-b)==0:
    day=day
else:
    day=day+1
#v<=(a-b)*day 낮 고려 안한다면.
#어차피 낮의 height만 v보다 같거나 높으면 저녁은 신경쓰지 않아도됨

    
print(day)

수식 설명: 

1. 달팽이의 현재 위치를 height라 하자.

2. 달팽이가 멈출 수 있을 때는 height>=v 일 때이다.

3. 낮의 달팽이의 현재 위치를 height라 하면, 밤의 달팽이의 현재 위치는 height-b. 즉 언제나 낮의 height>밤의 height.(b가 1보다 크므로)

4. 따라서 낮의 height 만 고려하면 된다. 

 

<낮의 height 고려 방법>
초기 위치=0

1일차

day1=0+a

night1=0+a-b=day1-b

2일차

day2=0+a-b+a=night1+a

night2=day2-b

 

그러므로 day(n)은 night(n)보다 항상 b만큼 크다. (위와 당연한 소리임)...(*)

그리고 day(n) 과 day(n-1)은 a-b의 차이이다.

 

따라서, 아주 대략적으로만 보자면 v<=(a-b)*day의 관계가 성립해야 하는데, 이 때 (*)에 의해 v에 b를 빼주면 day n에서의 맞는 비교가 된다. ->이것도 대략적이긴 한데 일단 그래서 (v-b)<=(a-b)*day의 관계가 성립하므로

day>=(v-b)/(a-b)

그런데 소수점은 day에 포함할 수 없으므로 if와 else문으로 나누어서 처리해주었다.

끝!

 

 

 

(논리 오류있을 수 있는데 일단 졸려서 여기까지 쓰고 1주일 후에 다시 생각해봐야겠다)