[Swift] 백준 게임 1072

1. 문제 이해

• (이긴게임 / 게임횟수) * 100 = 승률
• 승률이 변하는 최소 게임 횟수를 구하라.
• 앞으로 모든 게임에서 승리
• 승률이 변한다 == 승률이 높아진다
• 승률이 변하는 높아지는 최소 게임 횟수를 구하라.

2. 설계

• X : 게임횟수
• Y : 이긴 게임
• ( (이긴게임+N) / (게임횟수+N) ) * 100 = 승률 → ( (Y+N) / (X+N) ) * 100 = 승률
• 조건

• 1부터 10억까지 순서대로 연산은 시간 초과
• 이분탐색으로 최소 게임 횟수 구하기

3. 코드

• ( (Y+N) / (X+N) ) * 100 밑줄 친 부분이 실수가 됨
• 실수에서의 곱하기 연산 시 부동소수점 오류 발생
• 수정 → ( (Y+N) * 100 ) / (X+N)
• 예시) 0.99 * 100보단 9900/100가 안전
• 0.9899999999…, 0.333333333334와 같은 부동소수점 연산 특성상 오차 누적 가능성

import Foundation

func solution(){
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let X = input[0]
    let Y = input[1]
    let cur = (Y*100) / X // 현재 승률
    var left = 1
    var right = 1000000000
    var result = Int.max
    
    // 소수점을 무조건 버리기 때문에 이미 승률이 99퍼 이상일 때 변할 수 없음
    if cur >= 99{
        print("-1")
        return
    }
    
    // 이분탐색
    while left<=right{
        let mid = (left + right) / 2
        let n = ((Y+mid)*100) / (X+mid)
        if cur != n{
            right = mid - 1
            result = mid // 최소 게임횟수 찾기
        }else{
            left = mid + 1
        }
    }
    print(result)
}
solution()