9주차_#1072 게임

문제 이해 💬

원하는 Z가 되기 위한 X의 적정최솟값을 구하시오

• 게임 횟수 : X
• 이긴 게임 : Y (Z% : 승률. 소숫점은 버림)
• 앞으로 모든 게임에서 이김 (x가 늘어나면 반드시 Y 도 늘어남)
  X와 Y가 주어졌을 때, X를 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.

입력)
각 줄에 정수 X와 Y가 주어진다.
10 8

출력)
첫째 줄에 형택이가 게임을 최소 몇 판 더 해야하는지 출력한다. 만약 Z가 절대 변하지 않는다면 -1을 출력한다.
1

제한)
1 ≤ X ≤ 1,000,000,000
0 ≤ Y ≤ X

처음 든 생각🤔

X의 값이 조낸 크므로 일반적 서치로는 반드시 타임아웃이니 이진탐색이겠구만
적정 값을 찾는거니까 Parametic Search 겠구만

사실 아는게 이거밖에 없는게 이게 계속 나오네 ㅎㅎ..

핵심수식
z = int (y / x * 100)
중요
앞으로 모든 게임에서 지지 않는다

근데 이건 뭔가 '적정값을 맞추는 조건'이 수학식으로 쉽게 표현되는 편이니까,
이진탐색을 하는 범위조차 더 줄이는 수식을 만든다면 더 빨라질 것 같다.
이진탐색을 구현하고 여유가 남는다면 수학적 검증도 한번 해보쟈(니)

처음 짠 코드 👩🏻‍💻

x, y = map(int, input().split())
z = int(y/x*100)

# 이진탐색을 통해 적정 최솟값을 구하자!
# 적정 조건 : z가 1이 늘어나야함

# 이진탐색을 위한 시작점, 끝점
start = 0
end = 1000000001
result = 0
  
while (start <= end) :
  
  mid = (start + end) // 2
  tmp_z = int((y+mid)/(x+mid)*100)  # 적정 판단을 할 수 있는 값 계산

  # 승률이 더 낮아진 경우 오른쪽 부분 탐색
  if tmp_z <= z :
    start = mid + 1
  # 승률이 높아진 경우 왼쪽 부분 탐색
  else :
    result = mid # 최대한 덜 높였을때가 정답이므로, 여기에서 result  기록
    end = mid -1 


if result == 0 :
  print(-1)
else :
  print(result)

결과) 틀렸습니다

왜...?
예시 인풋 아웃풋 다 맞는데..? 왜죠...? why...........???????

좋은 해설과 코드 😇

추후 추가할 것 !