/ BOJ

BOJ_1072_게임_JAVA

문제 : 게임

링크 : BOJ_1072_게임

접근 방식

기존의 승률과 변동한 승률의 값을 비교하고, 그 값이 달라지는 가장 최소의 판수를 구하면 된다.

주어진 제한조건의 값의 범위가 매우 크기 때문에 통상적인 탐색으로는 시간초과가 날 것이라고 생각하여 이분 탐색으로 풀이했다.

소스 코드

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

public class BOJ_1072_게임 {

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine());

		long X = Long.parseLong(st.nextToken());

		long Y = Long.parseLong(st.nextToken());



		long end = X;

		long start = 0;

		long percent = ((Y*100) / X);

		if(X == Y) {
			System.out.println(-1);
			return;
		}
		boolean check = false;
		while(start <= end) {

			long half = (start + end)/2;

			long tempPer = (((Y+half)*100)/(X+half));

//			System.out.println("perc: "+percent+" tempper: "+tempPer + " start : "+start + " end : "+ end);

			if(tempPer != percent) {
				end = half;
				if(start == end) {
					check = true;
					break;
				}
			}else {
				start = half+1;

			}

		}

		if(!check) {
			System.out.println(-1);
			return;
		}

		System.out.println(end);

	}

}