[백준] 1072 게임 - 파라매트릭 서치(Paramatric Search) JAVA

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

1072번: 게임

코드설명

가장 먼저 문제를 보면, 완전탐색이 떠오릅니다. 

앞으로 김형택은 남은 모든게임을 이기므로, 한가지 방향으로 게임을 이기도록 처리하면서 완탐을 하면 될 것 같습니다만, 역시나 4%에서 시간초과가 발생합니다.

 

이 방식의 시간복잡도의 경우 O(X) 입니다. X의 범위는

• 1 ≤ X ≤ 1,000,000,000 으로써, 10^9 (10억)의 시간이 걸립니다. 

1억당 1초라고 가정하면, 최대 선형시간 시간복잡도 임에도 시간초과가 발생합니다. (10초임)...

 

또, 문제에서 

• 만약 Z가 절대 변하지 않는다면 -1을 출력한다.

라는 조건이 있습니다. 즉, 100퍼센트 일 경우는 절대 변하지 않다는 걸 알 수 있습니다.

100퍼센트뿐만이 아닌, 99퍼센트도 동일합니다. 소수점 버림으로 처리하기에 99.xxxx가 이전에 이미 계산되었다면, 아무리 많이 이겨도 이긴 횟수만큼 경기횟수도 늘어나기에 절대 변하지 않습니다.

 

구현하면서, 소수점 버림을 처리하는 부분에서도 문제가 발생했었습니다.

Math.floor라는 함수도 존재하지만, 해당 함수에 대해 잊고서 어떻게 구할 수 있을까 하면,

47/53 = 0.88xxxx 입니다.

이떄 0.88 * 100 을 통해 88로 만들면 처리할 수 있다고 생각했습니다.

 

하지만, 부동소수점 문제가 발생하여 너무 많은 값을 연산할경우 문제가 발생했습니다.

즉, 부동소수점 연산후 (long) Casting 을 하여 소수점을 버려도, 이미 오차가 발생한 상태입니다.

public static long getZ(long gameCount, long winCount) {
    return (long) ((  ( (double) winCount / (double) gameCount )  * 100.0)); 
}

 

해결방법은, 나누기 연산에 부동 소수점인 (double), float를 활용하지 않습니다.

public static long getZ(long gameCount, long winCount) {
    return (winCount * 100) / gameCount;
}

위와 같이 나눠질 숫자에 *100을 해서 몫만 가져오면, 정수 나눗셈으로 처리되어 문제가 발생하지 않습니다.

 

어떤분은 Math.floor를 활용하면 부동소수점 연산에서 자유로워질 수 있지 않을까? 할 수 있습니다.

public static long getZ(long gameCount, long winCount) {
    return (long) Math.floor(((  ( (double) winCount / (double) gameCount )  * 100.0))); 
}

하지만, Math.floor가 연산하기 전에 이미 부동소수점 연산이 반환된값을 버림처리하는 것 일 뿐이므로 여전히 오차가 발생합니다.

 

파라매트릭 서치를 이용합니다.

파라매트릭의 시간복잡도는 O(log N) 이므로, O(log 10^9) 입니다.

 

파라매트릭 서치 문제에서 가장 헷갈리는 점은, start와 end의 이동위치입니다.

이 문제같은경우, 최소한의 게임횟수를 구해야하기에 newZ > originalZ 라면 게임의 횟수인 middle값을 줄이기 위해 end = middle -1 을 처리합니다.

if( newZ > originalZ) { //새로운 승률이 원래 승률보다 크다면 최소값을 구하기 위해 middle값을 감소시킵니다.
    end = middle - 1;
}else {
    start = middle + 1;
}

 

 

만약 아래의 코드와 같이 처리할경우 같은경우까지 내려가게 되면서 middle값이 무조건 0으로 수렴합니다.

if( newZ >= originalZ) {
    end = middle - 1;
}else {
    start = middle + 1;
}

코드

완탐으로 처리한 코드입니다. 시간복잡도는 최악의 경우 O(X, 10^9)

package Main;

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

public class Main {
    public static int T, N;
    public static long X, Y, firstZ = 0, answer = 0;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
        X = Long.parseLong(st.nextToken());
        Y = Long.parseLong(st.nextToken());
        firstZ = getZ(X, Y);
        //앞으로 하는 모든게임에서 이긴다.
        if(firstZ >= 99) {
        	System.out.println(-1);
        	return ;
        }
        
        long startY = Y;
        long startX = X;
        long newZ = 0;
        answer = 0;
        while( (firstZ) == (newZ = getZ(startX++, startY++))) {
        	answer++;
        }
        System.out.println(answer);
        
        
    }
    
    public static long getZ(long gameCount, long winCount) {
//    	return (long) ((  ( (double) winCount / (double) gameCount )  * 100.0)); 
    	return (winCount * 100) / gameCount;
    }
    

}

 

파라매트릭 서치 코드 1

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


public class Main {
	
	public static long X, Y;
	public static long originalZ;
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	X = Long.parseLong(st.nextToken());
    	Y = Long.parseLong(st.nextToken());
    	
    	originalZ = ( Y * 100 / X )  ;
    	if(originalZ >= 99)
    		System.out.println("-1");
    	else 
    		paramatricSearch();
    	
    }
    
    public static void paramatricSearch() {
    	long start = 0;
    	long end = 2000000000;
    	long newZ = 0;
    	
    	while(start <= end) {
    		long middle = (start + end) / 2;
   
    		newZ =  (( Y + middle) * 100) / (X + middle) ;
    		
    		if( newZ > originalZ) { //새로운 승률이 원래 승률보다 크다면 최소값을 구하기 위해 middle값을 감소시킵니다.
    			end = middle - 1;
    		}else {
    			start = middle + 1;
    		}
    	}
    	System.out.println(start);
    	
    }
}

 

파라매트릭 서치 코드 2

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

public class Main {
    public static int T, N;
    public static long X, Y, firstZ = 0, answer = 0;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
        X = Long.parseLong(st.nextToken());
        Y = Long.parseLong(st.nextToken());
        firstZ = getZ(X, Y);
        if(firstZ >= 99) {
        	System.out.println(-1);
        	return ;
        }
        paramatric(0, X);
    }
    
    //최소 몇번 더 할 것인가가 매개변수이다.
    public static void paramatric(long lo, long hi) {
    	long start = lo; 
    	long end = hi;
    	while( start + 1 < end) {
    		
    		long middle = (start + end) / 2; // 
    		long newZ = getZ(X + middle, Y + middle );
    		//만약 새로운 승률이 맨처음 firstZ보다 작다면, 
    		//middle값 개수를 가장 줄여야 한다.
    		//만약 더 작다면, start값을 경기수를 늘려서 승률을 올려야 한다.
    		if(newZ <= firstZ) {
    			start = middle;
    		} else if(newZ > firstZ) {
    			end = middle;
    		}
    			
    	}
    	System.out.println(end);
    }
    
    
    public static long getZ(long gameCount, long winCount) {
//    	return (long) ((  ( (double) winCount / (double) gameCount )  * 100.0));
    	return (winCount * 100) / gameCount;
    }
    

}