[백준] 1072번: 게임 - JAVA

🔗 문제 링크

BOJ 1072번: 게임

1072번: 게임

 

1️⃣ 이분 탐색

📝 풀이 과정

새로운 게임을 하게 되면 계산되는 확률은 $((y+횟수) \times 100) / (x + 횟수)$

 

따라서 해당되는 횟수가 최소로 증가할 때 확률의 값이 변하는 경우를 찾으면 된다.

주어진 게임의 2배만큼 진행했는데도 확률이 변하지 않았다면 더이상 변하지 않기 때문에, 0부터 최고 1,000,000,000번 진행했을 때까지 이분탐색을 통해 값을 찾을 수 있다.

 

 

💡 부동소수점 오차

변수에 실수형을 저장하면 오차가 발생하게 된다.
실수형은 소수가 2진수로 저장되기 때문에 이를 나타낼 수 없을 경우 가장 근사한 값을 저장하기 때문이다.

예를 들어 double 변수에 0.58을 저장하고 *100을 한다면 58이 나온다고 생각할 수 있지만 컴퓨터는 이를 저장하지 못하고 0.5799999로 저장하기 때문에 실제로는 57이 반환된다.

따라서 실수를 계산할 때에는 최대한 정수범위 내에서 처리를 하거나 BigDecimal을 사용해야 한다.

 

⏱ 시간 복잡도

$O(\log 10^9)$

 

💻 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int z = getPercent(x, y);

        int ans = -1;
        int left = 0;
        int right = (int) 1e9;
        while (left <= right) {
            int mid = (left + right) / 2;

            if (getPercent(x + mid, y + mid) != z) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(ans);
    }

    static int getPercent(int x, int y) {
        return (int) ((long) y * 100 / x);
    }
}

 

📊 제출 결과

 

---

2️⃣ 수학

📝 풀이 과정

확률이 변하는 최소값은 z+1로 변했을 때이다.

 

이를 식으로 나타내면

$$\frac{(y+a)\times 100}{x+a} = z+1$$

$$100y+100a=(z+1)x+a(z+1)$$

$$a=\frac{100y-x(z+1)}{z-99}$$

 

따라서 a를 계산한 결과만큼 횟수를 증가시켜주면 답을 구할 수 있다.

a는 소수가 나올 수 있기 때문에 Math.ceil() 함수를 활용해 정수로 올림해주어야 한다.

 

단, 99%이상일 경우는 확률이 변하지 않는다.

99%는 아무리 게임을 많이 해도 100%가 될 수 없고, 100%는 증가할 수 없기 때문에 조건을 걸어주어야 한다

 

⏱ 시간 복잡도

$O(1)$

 

💻 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextInt(), y = sc.nextInt();
        int z = (int) (y * 100 / x);
        int ans = -1;

        if (z < 99) {
            ans = (int) Math.ceil((100 * y - x * (z + 1)) / (double) (z - 99));
        }

        System.out.println(ans);

    }
}

 

📊 제출 결과