BOJ - 1072 게임

leehyunjon·2022년 6월 27일

Algorithm

목록 보기

87/162

Problem

Solve

최소 몇번의 게임을 해야 승률이 바뀌는지 구해야한다.
일단 승률은 99%나 100%이라면 절대 변경되지 않는다.
그렇기 때문에 X = 1000000000, Y = 980000000으로 놨을때 승률이 98%가 된다.
여기서 승률이 변경되기 위해서는 1000000000이 되어야한다.

승률이 변경되는 게임 횟수를 이분탐색으로 찾기 위해 start=0, end=100000000로 놓고 이분탐색을 실행한다.

해당 승률을 구하기 위해 (Y/X)*100으로 승률을 구하고 승률이 변경되지 않았다면 횟수범위를 늘리기 위해 start = mid+1, 승률이 변경되었다면 최소 승률을 구하기 위해 end = mid로 설정한다.

하지만 이렇게 제출하면 틀리게 된다.

그 이유는 실수를 연산하는데 있어서 컴퓨터는 계산하기 너무 많은 소수점이 있다면 근사값으로 변경하는 경우가 있다. 이를 부동소수점이라고 한다.
예를 들어 X = 100, Y = 58로 놓고 (int)((double)Y/X)*100을 할 시 58이 아닌 57(.05799999)이 반환되게 된다.
실수 연산은 어렵기 때문에 최대한 정수범위 내에서 처리를 해야한다.
그렇기 때문에 (int)((long)Y*100/X)로 연산하여 실수가 아닌 정수 범위에서 승률을 구할 수 있도록 하자.

Code

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

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int X = Integer.parseInt(st.nextToken());
		int Y = Integer.parseInt(st.nextToken());

		long answer = -1;
		int originRate = (int)((Y * 100) / X);
		long start = 0;
		long end = 1000000000;

		while (start < end) {
			long mid = (start + end) / 2;

			//Y의 정수 크기를 감안해 long으로 타입 변환
			int rate = (int)(((long)((Y + mid) * 100) / (X + mid)));

			if (originRate != rate) {
				answer = mid;
				end = mid;
			} else {
				start = mid + 1;
			}
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}
}