백준 1072번 - 게임

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

1072번: 게임

 

 

 

 

 

이분탐색 문제이다. 처음에 이게 왜 이분탐색 알고리즘 문제인지 감이 안 잡혔지만..

 

1씩 더해가면서 승률이 바뀌는지 안바뀌는지 확인을 한다면, X Y가 클 경우 많은 시간이 걸릴 것이라는 생각이 들었다. 이분탐색 알고리즘을 사용하여 반씩 범위들을 좁혀가며 찾으면 효율적일 것이다.

 

 

탐색하는 수를 '게임을 몇 판 더 해야하는지'로 둔다. 그리고 그 수로 승률(Z)를 구한다. Z가 바뀌지않았으면 low값을 올리고, 바뀌었다면 high 값을 내리고 답을 갱신해나간다.

 

정답을 도출하는 데 주의할 점은 Z값이 절대 변하지 않는다면 -1을 출력하는 부분이다.

처음에는 승률이 100일 때의 경우만 있다고 생각했지만, 99인 경우도 변하지 않는다.

 

 

 

 

 

 코드

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

public class Game {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] input = br.readLine().split(" ");
		long X = Integer.parseInt(input[0]);
		long Y = Integer.parseInt(input[1]);
		
		long Z1 = (Y * 100) / X;
		long Z2 = (Y * 100) / X;
		
		long answer = 0;
		long low = 1; //추가하는 판 수 최솟값
		long high = X; //최댓값
		
		if(Z1 >= 99) { //Z가 절대 변하지 않음
			answer = -1;
		} else {
			while(low <= high) {
				long mid = (low + high) / 2;
				
				Z2 = ((Y + mid) * 100) / (X + mid);
				
				if(Z2 < Z1 + 1) { //Z가 바뀌지 X
					low = mid + 1;
				} else { //Z가 바뀌면
					high = mid - 1;
					answer = mid;
				}
			}
		}
		
		System.out.println(answer);
	}

}

 

 

 

 

 

결과