백준 1072 자바 - 게임 (boj 1072 java)

문제 : boj1072

 

  결국 n판 진행 후의 확률 차이가 1이면 n이 답이므로, 다음의 식을 구하면 풀 수 있는 문제이다. 이 때 x와 y는 이미 주어진 수치이므로 n에 대한 1차식이긴한데.. 난 수학적 지식이 딸려서 저걸 'n=~~' 형태로 변경할 수가 없었다 ㅠㅠㅠ

  

  그러므로 좀 더 무식한 방법으로 진행했다. 직접 해보는거다 ㅋㅋ

우선 '만약 Z가 절대 변하지 않는다면 -1을 출력' 부분부터 예외처리하고 넘어가야 한다.

간단히 말해 맨 처음 확률이 99%거나 100%면 변경될 수 없다. 이 경우 -1을 출력해주면 된다.

 

  다음으로는 간단히 100y/x를 구한 후, 해당 수치가 변경될 때 까지 n을 한땀한땀 증가시키면서 100(y+n)/(x+n)을 구해나가면 된다... 는 사실 이러면 시간초과가 난다. 생각보다 많이가야 확률이 변하는 케이스가 있는 것 같다. 따라서 약간의 백트래킹 아이디어를 넣었는데, 전부 보긴하는데 더 크게크게 보는 것이다. 적당한 수치의 GAP이란 값을 정해두고(내 경우엔 100000), 처음엔 'GAP' 만큼 증가시키면서 어떠한 구간에서 확률이 변화하는지 빠르게 찾는다. 만약 A번을 GAP씩 증가시켰을 때 확률이 변화되었다면, 정답은 GAP*(A-1)~GAP*A 사이에 있는게 된다. 따라서 해당 구간을 직접 1씩 증가시키면서 찾는다. 이 경우 최악의 케이스에서 총 B번이 필요한 테스트케이스가 있다면, 대략 O(B/GAP + GAP) 정도로 풀 수 있다.

 

  처음에 특정 수치를 정해두고 시작 위치와 해당 특정 수치 사이를 계속 탐색하며 이분탐색하는게 더 빠를 것 같긴한데 (O(logB)), B를 수학적으로 특정할 수가 없을 것 같아 위와 같이 했다. 결과적으로는 100ms도 안나온걸 보니 성공적이었던 것 같다.

 

 

코드 : github

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

public class Main {
    private static final int GAP = 100000;
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long x = Long.parseLong(st.nextToken());
        long y = Long.parseLong(st.nextToken());
        if (x==y) {
            System.out.println(-1);
            return;
        }
        int first = (int)(y*100/x);
        if (first == 99) {
            System.out.println(-1);
            return;
        }
        int cur = first;
        int cnt = 0;
        while (first==cur) {
            cnt+=GAP;
            cur = (int)((y+=GAP)*100/(x+=GAP));
        }
        
        cur = first;
        x-=GAP;
        y-=GAP;
        cnt-=GAP;
        while (first==cur) {
            cnt++;
            cur = (int)(++y*100/++x);
        }

        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}