[백준/Baekjoon] 1072 게임 C++ :: Binary Search

https://www.acmicpc.net/problem/1072

1072번: 게임

---

1. Logic

범위가 10억이기 때문에 이분탐색을 사용하여 풀이했다.

처음 승률은 y * 100 / 2이고 이분탐색으로 이긴 횟수를 바꿔가면서 카운팅 할 때는 (y + mid) * 100 / (x + mid)이다.

mid를 바꾸면서 승률이 변경되지 않으면 start를 mid로 올려 게임 수를 증가시키면서 처음 변경되는  end값을 찾아주면 된다.

승률을 구할 때 100을 곱해주기 때문에 int로 해주면 int의 범위를 벗어나기 때문에 long long으로 해줘야 한다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

long long x, y;
long long ex;
bool check(int mid) {
    long long res = (y + mid) * 100 / (x + mid);
    
    if(ex != res) return true;
    else return false;
}

long long solve() {
    long long start = 0;
    long long end = 1000000000;
    long long mid;
    
    if(!check(end)) return -1;
    
    while(start + 1 < end) {
        mid = (start + end) / 2;

        if(check(mid)) end = mid;
        else start = mid;
    }
    
    return end;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> x >> y;
    ex = y * 100 / x;
    
    cout << solve();
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90