백준 1072 - 게임 (자바 - 이분탐색)

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

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

 

* 예시

 

* 해결 과정

경기 횟수, 이긴 횟수, 이분탐색 시 사용할 start, end 모두 기본적으로 double 형을 사용해서 소수점까지 정확히 계산해준 뒤 int 로 형 변환을 해서 소수점을 버려줘야 한다.

우선 입력받은 게임 횟수와 이긴 횟수를 통해 기본 승률을 계산해준다.

- (int) (이긴 횟수 / (게임 횟수 / 100)) = 기본 승률

먄약 기본 승률이 99 보다 크거나 같다면 -1을 출력해준다. 기본 승률이 99 이상이라면 아무리 추가로 게임을 더 이기더라도 승률이 더 오를 수 없다.

승률이 99 에서 100 이 되려면 단 한번도 패배한 게임이 없어야 하는데 승률이 99라는 것은 단 한번이라도 패배한적이 있다는 뜻이다. 즉, 앞으로 몇 번을 더 이기더라도 승률을 1퍼센트 조차 올릴 수 없다.

 

만약 그렇지 않을 경우 아래의 로직을 수행한다.

1. start, end 를 선언하고 start 에 0, end 에 지금까지 플레이한 게임 횟수를 저장한다.

2. (int) start + 1 < (int) end 조건을 만족하는 동안 아래와 같이 반복문을 수행한다.

  - mid 에 (int)((start + end) / 2) 값을 저장한다. 여기서 mid 는 이번 반복문에서 계산에 활용할 추가 승리횟수를 뜻한다.

  - (int)((winCount + mid) / (gameCount + mid) / 100) 값을 계산하여 changeRate 변수에 저장한다. 이 변수는 추가된 승리횟수를 통해 변경된 승률이다.

  - 만약 기존의 승률보다 변경된 승률이 더 커졌다면. 즉, 승률에 변동이 생겼다면 end = mid 로 초기화해서 추가 승리횟수 범위를 크기가 작은 쪽으로 줄여준다.

  - 그렇지 않을 경우 start = mid 로 초기화해서 추가 승리횟수 범위를 크기가 큰 쪽으로 줄여준다.

3. 반복문이 끝나고 나면 end 값을 출력해준다. (승률에 변동이 있을 때 end 값을 초기화 하므로)

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] inputArray = br.readLine().split(" ");

        double gameCount = Integer.parseInt(inputArray[0]);
        double winCount = Integer.parseInt(inputArray[1]);

        int defaultRate = (int) (winCount / (gameCount / 100)); // 기본 승률
        if(defaultRate >= 99){
            bw.write("-1");
        }
        else{
            double start = 0;
            double end = gameCount;
            while((int)(start+1) < (int)end){
                int mid = (int) ((start+end)/2);
    
                int changeRate = (int) ((winCount+mid) / ((gameCount+mid)/100));
    
                if(changeRate > defaultRate){
                    // 승률 변동 있을 경우
                    end = mid;
                }
                else{
                    // 승률 변동 없을 경우
                    start = mid;
                }
            }
    
            bw.write((int)end + "");
        }      
        bw.flush();
        bw.close();
        br.close();
    }
}

 

수학적인 계산 결과에 따라 범위를 절반씩 줄여가며 탐색하므로 이분탐색 문제에 해당된다.