99클럽 코테 스터디 1일차 TIL (1072번: 게임)

문제

(시간초과) 지금까지 진행했던 게임만큼 1씩 더해가면서 승률이 바뀔 때까지 계산하기
- 주어진 게임 횟수(x)가 10, 이긴 게임(y)이 8인 경우에는 게임 횟수가 20일 때까지 승률이 변하는지 계산한다.
- 입력으로 주어지는 게임 횟수(x)의 최대값이 1 ≤ X ≤ 1,000,000,000 이기 때문에 최대 10억번 계산하므로 10초가 걸리게 되는데 시간 제한이 2초이므로 시간초과가 된다.
(불가능한듯?) 1을 더했을 때 추가되는 소수점을 계산하고 승률이 바뀌는 지점을 찾는다.
- float와 double은 부동소수점을 사용하기 때문에 소수점의 정밀도가 떨어져서 자세한 값을 찾기가 어렵다.
- BigDecimal을 사용하는 방법으로도 어떻게 해야하는지 잘 모르겠다.
(성공) 이분탐색

x: 게임 횟수

y: 이긴 게임

z: 승률

먼저, 주어진 게임 횟수만큼 계산을 했는데 승률이 변하지 않으면 절대 변하지 않는다고 판단하고 -1을 출력했다.

그 다음으로 앞으로 계산해야하는 게임 횟수만큼 이분 탐색을 하면서 값이 변하는지 확인하고, 그 범위를 좁혀가면서 최초로 변하는 지점을 계산했다. 아래 코드에서 z는 입력 값 x와 y를 가지고 미리 계산해 놓은 승률이다.