1072. 게임 (Swift, Python)

1072번: 게임

 

풀이

 이분탐색을 사용하여 해결하는 문제. 몇 번의 게임을 더 해야 하는지를 기준으로 잡으면 되는 간단한 문제였다. 간단한 문제인데 정답 비율이 낮았던건 Z를 구할 때 실수 연산에서 발생하는 오차때문인 것 같다. 처음 python으로 문제를 풀 때 Z를 구하는 식으로 다음과 같이 사용했다.

Z = math.trunc((Y / X) * 100)

 

 위와 같이 Z를 구했을 때 오답이 나왔는데 Y / X 연산에서 실수 관련해서 오차가 발생하기 때문이라는것 같다. 그래서 Y * 100 // X와 같이 식을 수정하니 정답이 나왔다. 정확하게는 모르겠으니 백준 사이트에서 질문 게시판을 참고하면 좋을 것 같다.

 

코드

[Swift]

var x: Int = 0
var y: Int = 0

if let input = readLine() {
    let inputs = input.split(separator: " ").map { Int($0)! }
    
    x = inputs[0]
    y = inputs[1]
}

var z: Int = y * 100 / x
var res: Int = -1

var left: Int = 1
var right: Int = 1000000000

while left <= right {
    // mid -> 추가로 진행하는 게임 수
    let mid: Int = (left + right) / 2
        
    let nx: Int = x + mid
    let ny: Int = y + mid
    let nz: Int = ny * 100 / nx
    
    // 승률이 변경되면 범위를 줄여서 더 작은 추가 게임 수를 찾는다.
    if z != nz {
        right = mid - 1
        res = mid
    } else {
        left = mid + 1
    }
}

print(res)

[Python]

if __name__ == '__main__':
    X, Y = map(int, input().split())
    Z = 100 * Y // X 

    left = 1
    right = 1000000000
    res = -1

    while left <= right:
        # mid -> 추가로 진행하는 게임 수
        mid = (left + right) // 2
        
        nx = X + mid
        ny = Y + mid
        nz = ny * 100 // nx

        # 승률이 변경되면 범위를 줄여서 더 작은 추가 게임 수를 찾는다.
        if Z != nz:
            right = mid - 1
            res = mid
        else:
            left = mid + 1
    
    print(res)