[백준] 1072. 게임

문제 링크

[백준] 1072. 게임

풀이 과정

다음은 수식을 활용한 풀이입니다.

$\frac{Y}{X}*100 = Z$ 이고, 판수를 더 올려 승률이 Z에서 변화하게 될 때의 승률은 무조건 감소하지 않고 증가하게 됩니다.

따라서, $\frac{Y+a}{X+a}*100 = Z+1$ 이 되는 a 값이 답이 됩니다. 왼쪽의 수식을 a로 정리하면, $a = \frac{xZ+x-100y}{99-Z}$가 됩니다.

위 수식을 통해 다음과 같이 답을 도출할 수 있습니다.

• 현재 승률 Z가 99 이상이면, 더이상의 승률 증가는 불가능하므로 -1을 출력합니다.
• 아니면, 분자를 분모로 나누어 a값을 계산합니다. 이 때, 나머지가 0이 아니면, 몫을 올림 처리 해줘야 하므로, 1을 더합니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long X = sc.nextInt();
        long Y = sc.nextInt();
        long Z = 100 * Y / X;

        if (99 - Z <= 0) {
            System.out.println(-1);
            return;
        }

        long q = (X * Z + X - 100 * Y) / (99 - Z);
        long r = (X * Z + X - 100 * Y) % (99 - Z);

        System.out.println(r == 0 ? q : q + 1);
    }
}

이분 탐색을 통해 문제를 해결할 수 있습니다.

while (low <= high) {
    let mid = Math.floor((low + high) / 2);

    if (getPercent(X + mid, Y + mid) != Z) {
        answer = mid;
        high = mid - 1;
    } else low = mid + 1;
}

판 수(X) 와 이긴 횟수(Y)를 mid 만큼 늘려 승률을 계산합니다.

• 승률에 변동이 생기면, 해당 횟수 answer 에 담고, 더 적은 횟수로 승률 변동이 있는지 확인하기 위해 상한값을 조정합니다.
• 변동이 없다면, 더 많은 게임 횟수 범위 내를 확인하기 위해 하한값을 조정합니다.

코드

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 low = 0, high = (int) 1e9;
        int answer = -1;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (getPercent(X + mid, Y + mid) != Z) {
                answer = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        System.out.println(answer);
    }

    static int getPercent(int X, int Y) {
        return (int) ((long) 100 * Y / X);
    }
}