C++ ) 1072 게임

Blue·2023년 5월 18일
0

접근

게임 횟수가 X 이고 이긴 게임이 Y 이다. 그리고 Z 는 승률이 된다.
이말은 100 번중 80번을 이겼다면 Z 는 80%가 되는것이다.

하지만 이긴 게임이 늘어난다면 게임 횟수도 그에 따라 늘어나게 될것이다.
초기 X,Y 를 가지고 승률을 받았으면 X와 Y를 1씩 늘리면서 승률이 변하는 순간에 답을 내면 된다.

하지만 X,Y 의 범위는 1<=X <= 1000000000 이다.X 가 최대일떄 10억이기에 초기값부터 마지막값 까지 1씩증가하면서 값을 변하는걸 확인한다면 10초가 걸리게된다.

그래서 초기 값과 최대값 10억의 값을 각각 주어서 이분탐색으로 적절한 값을 찾으면 되는것이다.
최소값을 찾아야하기에 처음 기준인 5억일때 값이 변하면 high 를 mid-1 로 하여 다음값을 찾고
다음은 2억5천일때 ,,,, 1억25천일떄,,,,계속 하다 최소로 값이 변하는 부분이 원하는 Z 일것이다

코드

#include <iostream>

using namespace std;

double lowX,lowY,temp,init_X;
double highX=10000000000,highY;

int Z,temp_Z,ret,mid;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lowX >> lowY;
    Z=(lowY*100)/lowX;
    temp=(lowX-lowY);
    init_X=lowX;
    
//    cout << Z << "\n";
    
    if(Z>=99) {
        cout << -1 << "\n";
        return 0;
    }
    else {
        
        while(lowX<=highX) {
            mid=(lowX+highX)/2;
            highY=mid-temp;
            
//            cout << mid << " " << highY << " " << temp << "\n";
            
            temp_Z=(highY*100)/mid;
//            cout << temp_Z << "\n";
            
            if(Z!=temp_Z) {
                ret=mid-init_X;
                highX=mid-1;
            }
            else {
                lowX=mid+1;
            }
        }
    }
    
    cout << ret << "\n";
    
    return 0;
}

틀린 이유

Y를 X 로 나누어서 100을 곱해주는 방식으로 정답률을 냈는데 이렇게 하니까 자꾸 오답이 나왔다
Y*100/X 를 하니,, 답이 나왔다,,, 이건 솔직히 왜 이렇게 되는지 정확히 모른다

아마 부동소수점 부분일텐데 , 이 부분은 조금 더 공부를 해야할것 같다

profile
할수있다가 아닌 해야한다!!

0개의 댓글