[알고리즘] 백준 1072번 - 게임(Java)

1072번: 게임 (acmicpc.net)

1072번: 게임

 

문제

김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.

이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.

게임 기록은 다음과 같이 생겼다.

• 게임 횟수 : X
• 이긴 게임 : Y (Z%)
• Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.

X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.

입력

각 줄에 정수 X와 Y가 주어진다.

출력

첫째 줄에 형택이가 게임을 최소 몇 판 더 해야하는지 출력한다. 만약 Z가 절대 변하지 않는다면 -1을 출력한다.

제한

• 1 ≤ X ≤ 1,000,000,000
• 0 ≤ Y ≤ X

 

* 풀이

해당 문제는 이분 탐색으로 풀 수 있는 문제다. 테스트케이스가 매우 크므로 바로 이분 탐색이 떠올랐다. 최소 판수(int start = 0)를 지정하고, 최대 판수(int end = (int)1e9)를 지정한다. 그 후 승률을 구하는 메서드(getPercent())와  start, end를 binarySearch() 메서드의 파라미터로 넘겨준다. mid를 계산한 후 변수 z에 getPercent(x + mid. y + mid)를 함으로써 값을 저장한다. 그 후 target(기존 승률)과 z를 비교하면 되는데, z와 target이 다른 경우 숫자가 너무 크므로 숫자를 줄여줘야 한다. 따라서 end = mid - 1;를 해주어야 한다. 반대로 z와 target이 같은 경우에는 숫자를 크게 해야 하므로 start = mid + 1;를 해주면 된다. 그 후 이분 탐색을 돌리면서 cnt를 갱신해주면 풀이는 완료된다.

import java.util.*;

public class Main {

    static int cnt = -1;
    static int x;
    static int y;

    public static void binarySearch(int start, int end, int target) {
        while(start <= end) {
            int mid = (start + end) / 2;

            int z = getPercent(x + mid, y + mid);

            if(z != target) {
                cnt = mid;
                end = mid - 1;
            }

            else {
                start = mid + 1;
            }
        }
    }

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        x = sc.nextInt();
        y = sc.nextInt();

        int start = 0;
        int end = (int)1e9;

        binarySearch(start, end, getPercent(x, y));
        System.out.println(cnt);
    }
}