[JAVA]백준 1072번: 게임

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

1072번: 게임

1. 문제 설명

 

현재까지의 게임 횟수 X, 이긴 게임 Y이 주어진다.

지금부터 형택이는 게임을 하면 무조건 이긴다고 할 때 게임을 최소 몇 판을 해야 승률이 변하는지 구하는 문제.

 

2. 풀이

 

2가지로 풀이가 가능하다.

 

두 방법 모두 Z가 100, 99 일 때는 -1을 출력하고  98 이하일 때부터 계산을 수행한다.

 

99,100일 때 -1을 출력하는 이유는 99,100일 때는 아무리 게임을 더 하더라도 Z를 바꿀 수 없다..

 

1. 이분탐색

- start=0, end=2*10^9로 하여 이분 탐색을 진행한다.

- X만큼 게임을 더 진행했을 때 Z와 같거나 작을 경우 mid 아래 구간 삭제.

- X만큼 게임을 더 진행했을 때 Z보다 큰 경우 mid 윗 구간 삭제.

 

2. 수식

- 최소 N만큼 게임을 더 진행해야지 Z가 바뀐다고 가정하자.

- (Y+N)/(X+N)*100=> Z+1 수식을 계산하면 N=> XZ+X-100Y/(99-Z)

- 따라서 N이 될 수 있는 최솟값은 XZ+X-100Y/99-Z, XZ+X-100Y/99-Z + 1 (소수점 고려)

 

부동소수점 오차로 인해서 많이 틀렸다.

 

가능하면 double 형 말고 long 형으로만 계산을 해야지 틀리지 않을 수 있다.

 

3. 코드

 

1) 이분 탐색

import java.awt.*;
import java.io.*;
import java.util.*;

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));

        long X, Y;

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

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

        long Z = 100 * Y / X;

        if (Z >= 99) {
            bw.write("-1");
        } else {

            long start = 0;
            long end = 2000000000;

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

                long ret = 100 * (Y + mid) / (X + mid);

                if (ret> Z) {
                    end = mid;
                } else {
                    start = mid + 1;
                }
            }

            bw.write(String.valueOf(end));
        }


        bw.flush();

    }




}

2) 수식

import java.awt.*;
import java.io.*;
import java.util.*;

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));

        long X, Y;

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

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

        long Z;

        if (X == Y) {
            bw.write("-1");
        } else{

            Z = 100 * Y / X;

            if (Z == 99) {
                bw.write("-1");
            } else {
                long one = (X * Z + X - 100 * Y);
                long two = 99 - Z;
                long mid = one / two;

                if (one % two == 0) {
                    bw.write(String.valueOf(mid));
                } else {
                    bw.write(String.valueOf(mid + 1));
                }
            }
        }


        bw.flush();

    }




}