백준 2869번 python 풀이

달팽이 문제를 풀다가 또 막혀버렸다

 

 

처음에 생각한 방법은

 

V미터를 A미터로 나눈 몫을 각각 A와 B에 곱해서 빼고 더하는 방식이었는데

 

테스트 케이스를 해보고 time 함수로 시간도 재봤지만 결국 시간초과로 실패...

 

<초기코드>

 

import sys, time

a, b, v = map(int, sys.stdin.readline().split())

start = time.time()

count = 1
r = 0

while True:  
  #print("v: " + str(v) + ", c: " + str(count) + ", r: " + str(r))
  if v <= a:
    print(count)
    break
  else:
    r = v // a
    count += r
    v = v - (a * r) + (b * r) 
    #print("v: " + str(v) + ", c: " + str(count) + ", r: " + str(r))

print("time: ", time.time() - start)

 

반례를 찾기 어려웟는데 고수분의 도움으로 반례를 찾았다

 

input: 100000000 99999999 1000000000

print: 900000001

time: 약 400초가량

 

우선 위의 코드는 결과는 정상이지만

 

반복문을 돌릴때 A와 B와 V가 모두 크면서 A와 B 값의 크기 차이가 근소할때 시간초과 문제가 발생한다

 

반례를 예시로 들면 A와 B값의 차이는 1이기 때문에 엄청 오래 반복문을 돌게된다...

 

실제로 카운트 해본결과 282896825번을 반복했다...

 

그래서❗❗ 반복문을 최소로 돌릴 수 있는 방법을 생각하다가.. 포기했다...

 

이럴땐 고수분들의 솔루션을 봐야하기에 서칭을 했는데

 

아니!! 이렇게 간단할 줄이야...😭

 

결론적으로 참고해서 만든 코드는 아래와 같다

 

<최종코드>

import sys

a, b, v = map(int, sys.stdin.readline().split())

r = (v-b) // (a-b)

if (v-b) % (a-b) == 0:
  print(r)
else:
  print(r + 1)

 

생각해보면

 

V ≤ 일자 *A - 일자*B가 성립하기 때문에 해당 식을 적용하는 것 같다

 

위의 식에서 왜 분모에 -B를 해주는지 이해가 안돼서 찾아봤는데

 

이미 정상에 오른 경우엔 다시 미끄러지지 않는 경우를 고려해서 미리 b만큼을 빼주기 위해서 라는 뜻으로 이해했다