99클럽 코테 스터디 1일차 TIL - 백준 1072 Swift

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	1072	게임	이분탐색	실버3	Swift

🚀 나의 접근 방법

경우의 수가 많아 보여 이분탐색으로 접근했다. 이분탐색은 log(N)의 시간 복잡도이며 많은 경우의 수를 확인해야 하는 때에 적합하다.

이분탐색을 하려면 탐색 데이터가 필요한데 그게 무엇일까??

문제에서 '앞으로의 모든 게임에서 지지 않는다'라고 했으니 적어도 처음에 입력 된 게임 횟수 X 만큼 더 이기면 승률은 무조건 올라가지 않을까 생각했다.

그래서 결국 1 ~ X(게임 횟수)의 모둔 수로 이분탐색 하면서 승률을 계산하고 비교 하는 것이다.

✍️ 나의 코드

let input = readLine()!.split(separator: " ").map{ Int($0)! }
let (x, y) = (input[0], input[1])
let z = y * 100 / x

var start = 0
var end = x
var result = -1

while start <= end {
    let mid = (start + end)/2

    let nx = x + mid
    let ny = y + mid
    let nz = ny * 100 / nx
    
    if z < nz {
        result = mid
        end = mid - 1
    } else {
        start = mid + 1
    }
}

print(result)

🤔 회고 및 개선사항

승률 계산하기

처음에는 승률을 아래와 같이 계산했다. 그랬더니 당연히 Int형의 연산이기 때문에 y / x의 값은 0이 나왔다.

(y / x) * 100

다시 아래와 같이 수정해서 굳이 Double형으로 변환 하지 않고 승률을 계산할 수 있었다.

y * 100 / x

탐색 데이터 범위 결정

처음에는 1 ~ 1,000,000,000로 문제를 통과 했지만 생각해 보니 '굳이 저 범위 까지 해야 되나' 라는 생각이 들었다.
1 ~ X(게임 횟수)로도 충분할 것 같았고 무사히 통과했다.