[백준] 1072번 : 게임 - C/C++

 

문제에서 요구하는 것은 간단하다.

몇 번의 게임을 반복해서 승률을 높일 수 있는지를 구하는 것이다.

 

여기서 주의해야할 점은 게임의 횟수 변수의 타입이다.

int형으로 설정하는 것이 아닌 long long 으로 설정해야한다.

 

문제 설명에서 x는 10억까지 올 수 있다고 하니,

64비트 정수를 표현할 수 있는 long long 을 사용하자.

 

승률(z) 공식은 어떻게 될까?

int z = (y / x) * 100;

 

이렇게 쓰면 틀린다.

왜요?

정수 나눗셈 → 곱셈 순서이기 때문에 소수점은 날아가면서 실제 승률보다 낮게 나올 가능성이 있다.

y = 80, x = 100 이라면

y/x = 0 이 되어버리면서 0*100 이라는 말도 안 되는 계산을 해야할 수도 있기 때문이다.

 

아래와 같이 승률 공식을 바꾸자.

int z = (y * 100) / x;

 

 

승률이 더이상 오를 수 없는 경우는 언제일까?

소수점은 무시한다고 했으니 승률 99%가 최대일 것이다.

아무리 게임을 더 한다고 해도 승률이 100%가 될 수는 없다.

728x90

여기까지는 쉽게 코드를 작성했는데, 그 다음이 고비였다.

힌트 참고

 

이분 탐색(이진 탐색)으로 풀자 !!

 

게임을 최소 한 판부터 10억 판까지 할 수 있으니, 초기값을 설정해주자.

ll low = 1;
ll high = 1000000000;

 

ll 은 long long 타입인데 길게 쓰기 싫어서 미리 선언해준 것이다.

어떻게 하냐면

typedef long long ll;

 

이렇게.

 

근데 보통 카운트 수를 올리는 알고리즘은 '부르트포스'를 사용하는 것 같은데,

여기서는 왜 알고리즘 분류가 '부르트포스'가 아닌 '이분 탐색'일까 생각을 해봤다.

부르트포스는 하나부터 (원하는 값을 찾을 때)끝까지 탐색을 하는 것이기 때문에 부르트포스로 구현하게 되면 시간 초과가 날 것 같긴했다.

생성형 ai (챗지피티)에게 물어보니 맞다고 한다.

 

게임을 mid 번 더 했다고 가정해보자.

while(low <= high){
    ll mid = (low + high) / 2;
    int z2 = ((y + mid) * 100) / (x + mid);
    ...

 

z2는 새로운 승률이다. 

mid 판을 모두 이긴다고 가정하므로,

총 게임에서 이긴 수 = y + mid

총 게임 수 = x + mid

가 된다.

그러므로 새로운 승률 z2는 아래와 같이 식을 수정할 수 있다.

int z2 = ((y + mid) * 100) / (x + mid);

 

이분 탐색(이진 탐색) 루프 코드를 구현했으니, 이제 승률이 올라가는 조건을 알아보자.

    if(z2 > z){
        ans = mid;
        high = mid - 1;
    } else {
        low = mid + 1;
    }

 

z2 가 z 보다 크다면 승률이 변한 것이다.

정답 후보로 올려두고 최댓값(high)를 하나 줄이자.

 

만약 z2 가 z 보다 작거나 같다면 승률에 변화가 없는 것이기 때문에 최솟값인 low를 하나 늘려준다.

 

이제 축적(?)된 ans를 출력해주면 끝이다.

 

 

전체 코드

#include <iostream>

//게임
using namespace std;
typedef long long ll;

int main(){
    ll x, y;
    cin >> x >> y;
    int z = (y * 100) / x; 

    if(z >= 99){
        cout << "-1" << '\n';
        return 0;
    }

    ll low = 1;
    ll high = 1000000000;
    ll ans = -1;

    while(low <= high){
        ll mid = (low + high) / 2;
        int z2 = ((y + mid) * 100) / (x + mid);
        if(z2 > z){
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    cout << ans << '\n';
}

 

 

난이도 실버3의 문제였다. 승률 계산에서 실수를 했다. 정수로 만드는 것이어서 0이 나올 것이라는 생각을 처음에는 못했던 것 같다. '알고리즘 분류'는 최대한 안 보면서 풀고 싶은데 아는 것도 많이 없다보니 계속 보게 되는 것 같다.. 이 부분을 조금 많이 고쳐야할 것 같다. 더 많은 문제를 통해서 문제를 읽고 어떻게 풀어야할지 감이 오는 정도로 성장하고 싶다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️