[백준] 1072번 : 게임 - Java

문제

https://www.acmicpc.net/problem/1072

현재 진행한 게임 수와 이긴 게임 수가 주어질 때, 승률을 1% 이상 올리기 위해 추가로 진행해야 하는 최소 게임 수를 구하는 문제입니다. 승률은 (이긴 게임 수 / 총 게임 수) * 100 으로 계산됩니다.

 

접근 방법

• 이분 탐색: 추가로 진행할 게임 수를 이분 탐색을 통해 효율적으로 찾습니다.
• left, right, mid를 사용하여 이분 탐색을 수행합니다.
  • mid는 추가로 진행할 게임 수의 중간값을 나타냅니다.
  • 새로운 승률을 계산한 후, 현재 승률과 비교하여 조건에 맞게 left 또는 right를 조정합니다.
• 현재 승률 계산: (int) ((long) wonGames * 100 / totalGames)를 통해 현재 승률을 계산합니다. 여기서 long 타입을 사용하는 이유는 곱셈에서 발생할 수 있는 오버플로우를 방지하기 위해서입니다.
• 새로운 승률 계산: 중간값을 이용해 새로운 승률을 계산하고, 현재 승률과 비교합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int totalGames = Integer.parseInt(st.nextToken());
        int wonGames = Integer.parseInt(st.nextToken());
        int currentWinRate = (int) ((long) wonGames * 100 / totalGames);
        int answer = -1;
        int left = 0;
        int right = (int) 1e9;

        while (left <= right) {
            int mid = (left + right) / 2;
            int newWinRate = (int) ((long) (wonGames + mid) * 100 / (totalGames + mid)); // 새로운 승률 계산

            if (newWinRate > currentWinRate) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(answer);
    }
}

메모리:14276kb 시간:128ms