BOJ-1072 게임 Swift

문제

김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.

이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.

게임 기록은 다음과 같이 생겼다.

• 게임 횟수 : X
• 이긴 게임 : Y (Z%)
• Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.

X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.

입력

각 줄에 정수 X와 Y가 주어진다.

출력

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

내가 푼 풀이

- 이문제를 어떻게 풀어야하는지 고민하는건 어렵지않았으나, 계산의 정확성에서 틀렸다.

- 앞으로 모든 게임을 이긴다고 했으니, 추가로 하는 판들은 모두 Y에 더해진다.

- 최소 한판부터 최대 게임횟수까지 이분탐색으로 Z값이 변하는 최솟값을 구하면된다.

- 여기서 승률을 구하는 문제에서 Double캐스팅후 계산을 했어도 정확성에 문제가 있었다.

- 100 * ( Y / X )로 구했다가 Int는 소숫점이 날아가고, Double은 큰값을 계산할때 정확성에 문제가 생겼다

- Y를 100 먼저 곱해준다음 X로 나눴더니 문제가 풀렸다 -> 100 * Y / X

- 이렇게 구한 새로운 승률이 기존승률과 같다면 승수를 더 늘린다. 승률이 올랐다면, 승수를 내려서 최솟값을 찾는다.

 

import Foundation

//입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let X = input[0], Y = input[1]
let Z = Y * 100 / X

// result = -1 (한판도 하지않는경우와 승률이 변하지않는경우)
// startIndex: 0, endIndex: X
var result = -1
var start = 0
var end = X

// 이분탐색
while start <= end {
    let mid = (start + end) / 2
    let newX = X + mid
    let newY = Y + mid
    let newZ = 100 * newY / newX
    // 승을 더해서 계산한 승률이 이전승률과 같다면, 승수를 늘려서 승률을 다르게 만든다.
    // 승을 더해서 계산한 승률이 이전승률과 다르다면, 승수를 줄여서 최솟값을 구한다
    if newZ == Z {
        start = mid + 1
    } else {
        result = mid
        end = mid - 1
    }
}
print(result)