[Python] 이분탐색- 19592. 장난감경주(실5)/Parametric search

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

19592번: 장난감 경주

---

2. 핵심 아이디어

2-1) 0이 출력되어야 할 경우

- 이미 우승(즉 내가 가장 빠를 때)

 

2-2) 빠르기를 어떻게 측정할 것인가

: 빠르기를 측정하는 수단은 여러가지가 있다.

 

같은 단위의 속력이 될 수도 있고 시간이 될 수도 있다.

여기서 속력으로 빠르기를 측정하려면 부스터 + 일반속도를 가중평균내어야 한다.

 

따라서 상대적으로 더 쉬운 [도착 시간]을 기준으로 빠르기를 측정했다.

 

2-3) 최적 값을 어떻게 출력?

=> 이분탐색을 통해 z의 최솟값을 찾을 때까지 이동

 

---

3. 코드

n= int(input())

for _ in range(n):
    #차의 개수 / 트랙 길이 /최대 부스터 제한 받기
    car_num, track, max_boost = map(int, input().split())
    
    #차의 속력 받기
    v=list(map(int, input().split()))

    #나를 제외한 가장 빠른 사람의 도착시간은?
    victory = track/ max(v[:-1])

    #내가 이미 짱이라면 -> 0출력
    if v.index(max(v))==car_num-1:
      print(0)

    #아니라면-> 부스터 쓰자
    else:

      start=0
      end = max_boost
      result=0
      
      #start-end 사이 이분탐색
      while(start<=end):
        mid= (start+end)//2
        #total ->도착시간
        total =(track-mid)/v[-1] +1

        #더 빠르다면-> z값이 최소가 되어야 하므로 end=mid-1/결과 갱신
        if total<victory:
          end=mid-1
          result= mid
        #더 느리다면-> 부스터 출력 늘리기 : start= end+1
        else:
          start= mid+1
      
      #최대 제한범위에 있는지 확인
      if(result <=max_boost):
        print(result)  
      else:
        print(-1)

---

4.배운 점

탐색 티가 나는 이분탐색 문제들은 가볍게 구현해내지만

패러매트릭 서치 문제에는 아직 이분탐색을 적용하기 힘든 모습들이 보인다.

 

최적값 문제는 대부분 이분탐색을 활용할 수 있다는 사실을 알아두자.