이분탐색을 이용해서 풀었지만 이해가 안 가는 부분을 정리

처음 작성한 코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll x, y, z, mid, ret;

bool check(ll mid) {
	z = ((double)((double)y * 100.0 / x));
	ll temp = (double)((double)(y + mid) * 100.0 / (double)(x + mid));

	if (temp - z >= 1) return 1;
	else return 0;

}

int main() {
	cin >> x >> y;

	ll l = 1; ll r = 1e18 + 4;
	
	ret = 0;
	
	while (l <= r) {
		mid = (l + r) / 2;
		if (check(mid)) { //변한 경우
			ret = mid;
			r = mid - 1;
		}
		else { //dosent change
			l = mid + 1;
		}
	}
	if (ret == 0)cout << -1;
	else cout << ret << "\n";

}

문제풀이 : 몇번 더 경기를 하는 횟수를 이분탐색으로 탐색. 앞으로 하는 경기는 무조건 이기기 때문에 전체 경기 증가 + 이긴 횟수 증가가 되면서 승률인 z가 변하게 되는 것을 탐색한다.

하지만 처음 작성한 코드를 제출하면 계속 틀린다.

check 함수를 만들어서 판단.

처음 코드가 틀린이유(1)

bool check(ll mid) {
	z = ((double)((double)y * 100.0 / x));
	ll temp = (double)((double)(y + mid) * 100.0 / (double)(x + mid));

	if (temp - z >= 1) return 1;
	else return 0;

}

당연히 소숫점으로 계산해야한다고 생각해서 long long 타입을 double로 바꿔서 계산했다. 100.0을 곱해서 계산했다.

하지만Z를 정수값으로만 사용할 수 있다면, 실수 연산을 할 필요가 없었다. 이유는 문제의 조건 때문이니다. Z는 Y / X 비율에 기반한 “백분율” 값이며, Z가 항상 정수로 올림(또는 내림) 처리된 값으로 비교하기 때문에 실수 연산을 할 필요가 없었다.

처음 코드가 틀린 이유(2)

ll l = 1; ll r = 1e18 + 4;

r을 너무 큰 값으로 설정했다. 사실 너무 큰 값으로 했다는 것을 알고는 있었지만 상한값을 어느 정도로 해야할지 모르겠어서 그냥 long long 이 받을 수 있는 것 중 큰 값으로 설정했다. 하지만 계속 틀렸다고 나왔고 이 부분을 1e9로 바꾸기만 하면 정답처리가 됬다.

1e18이 너무 커서 비효율적인 것을 이해가 갔지만 이게 시간초과도 아니고 아예 틀렸다고 나오는 것은 이해가 가지 않았다. 하지만 1e18로 설정할 경우 오버플로우 문제가 발생할 수 있었다.

(a) 만약 mid가 1e18에 가까운 매우 큰 값일 때 (y + mid) * 100 / (x + mid)

y + mid 또는 x + mid 자체는 long long 범위 내에 있을 수 있습니다.

그러나 (y + mid) * 100은 102010^{20}1020에 가까워질 수 있습니다. 이는 long long의 표현 범위를 초과해 오버플로우를 일으킵니다.

b) 이진 탐색의 잘못된 판단

mid 값이 1e18까지 커질 수 있다면, 계산 결과가 오버플로우로 인해 잘못된 값이 나오므로:

• 실제로 승률이 증가했음에도 불구하고 조건문 (y + mid) * 100 / (x + mid) > z가 제대로 작동하지 않습니다.
• 이로 인해 이진 탐색이 잘못된 방향으로 진행되거나 종료 시점에서 틀린 답을 반환합니다

이런 이유로 틀렸다고 나오는 것이었다… 틀린부분을 모두 수정했더니 맞을 수 있었다.

수정한 코드(정답)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll x, y, z, mid, ret;

bool check(ll mid) {
    ll new_z = (y + mid) * 100 / (x + mid); // 새로운 승률
    return new_z > z; // 기존 승률과 비교, new_z가 변했다면 무조건 기존 z보다 클것!
}

int main() {
    cin >> x >> y;

    ll l = 1; 
    ll r = 1e9 + 4; // 최대 범위를 현실적으로 설정
    z = y * 100 / x; // 기존 승률
    ret = 0;

    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) { // 승률이 증가하는 경우
            ret = mid;
            r = mid - 1; // 더 작은 mid 값을 탐색
        }
        else { // 승률이 증가하지 않는 경우
            l = mid + 1; // 더 큰 mid 값을 탐색
        }
    }

    if (ret == 0) cout << -1;
    else cout << ret << "\n";

    return 0;
}

헷갈렸던 부분 정리

y/x * 100 은 안되고 (y*100) / x 은 가능?

처음에 문제를 풀때 보통 백분율을 계산 하듯이 y/x 비율을 구한후 100을 곱해 백분율을 구하는 식 y / x * 100을 작성했지만 계산이 잘 되지 않았다.

찾아보니 (y*100)/x을 사용해서 계산해야 했다. 둘다 같은 식이여서 바꿀 수 있다는건 이해가 가는데 왜 y / x * 100식이 틀렸는지는 이해가 안갔다. 그래서 찾아봤더니..

internet :

(y / x) * 100과 (y * 100) / x는 결과적으로 같은 값을 계산하는 것처럼 보이지만, 정수 연산의 특성 때문에 큰 차이가 발생-> 차이는 정수 연산의 중간 값 손실 및 순서에 따른 오차

1. (y / x) * 100의 문제

a) 순서에 따른 값의 손실

C++에서 y와 x가 모두 int 또는 long long 타입이라면, y / x는 정수 나눗셈입니다. 정수 나눗셈에서는 소숫점 이하가 버려지기 때문에 값의 손실이 발생합니다.

예를 들어:

• y = 47, x = 53이라면: y/x=47/53=0.8867…(실수 연산 기준)y / x = 47 / 53 = 0.8867\ldots \quad (\text{실수 연산 기준})y/x=47/53=0.8867…(실수 연산 기준) 하지만 정수 연산에서는: y/x=0(소수점 이하 버림)y / x = 0 \quad (\text{소수점 이하 버림})y/x=0(소수점 이하 버림)
• 이후 * 100을 하면: (y/x)∗100=0∗100=0(y / x) * 100 = 0 * 100 = 0(y/x)∗100=0∗100=0 이는 정확한 승률을 계산하지 못하는 결과를 초래합니다.

2. (y * 100) / x의 장점

a) 곱셈을 먼저 수행

(y * 100)은 정수 곱셈으로 먼저 계산되며, 이 결과를 x로 나눕니다. 이렇게 하면:

• 정수 나눗셈의 손실이 최종적으로 한 번만 발생합니다.
• 곱셈이 먼저 이루어지므로 더 많은 유효 자릿수를 유지할 수 있습니다.

예를 들어:

• y = 47, x = 53이라면: y∗100=4700y * 100 = 4700y∗100=4700 이후: (y∗100)/x=4700/53=88(정수 연산 기준)(y * 100) / x = 4700 / 53 = 88 (\text{정수 연산 기준})(y∗100)/x=4700/53=88(정수 연산 기준) 이 값은 승률 계산의 올바른 결과를 제공합니다.

b) 오버플로우 방지

(y * 100)에서 y와 100의 곱이 long long 타입 범위 내에 있다면, 정확한 값을 유지한 상태로 나누기를 수행합니다.

• y,x≤109y, x \leq 10^9y,x≤109이라면, y×100≤1011y \times 100 \leq 10^{11}y×100≤1011, 이는 long long 범위에 안전하게 포함됩니다.

3. 정확한 비교

결론!

(y / x) * 100은 정수 연산으로 인해 소수점 이하가 버려지는 문제가 있고, 정확한 승률 계산이 불가능합니다. 반면, (y \* 100) / x는 곱셈 후 나눗셈을 수행하므로 계산이 정확하며, 정수 연산 특성을 제대로 활용합니다.

따라서 승률을 비교하거나 계산하는 문제에서는 반드시 (y * 100) / x 방식을 사용