99클럽 코테 스터디 1일차 TIL : 이분탐색(백준1072. 게임)

 

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

 

 

 

---

 

[1차 풀이]

 

예제1)
10 8 => 승률 80
11 9 => 승률 81

예제2)
100 80 => 승률 80
101 81 => 승률 81

예제3)
47 47 => 승률100(최대)
더이상 안올라감
-1

예제4) 
99000 0 => 승률0
100000 1000 => 승률1

* 탐색
승률이 1프로올라가면 멈춤

package search;

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

public class Ex1072 {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);
		
		float x = 0;
		float y = 0;
		
		if(st.hasMoreTokens()) {
			x = Float.parseFloat(st.nextToken());
			y = Float.parseFloat(st.nextToken());
		}

		int z = Float.valueOf((y/x)*100).intValue();	//현재 승률
		int result = 0;
		
		if(x==y) {
			result = -1;
		} else {
			for(int i=1;i<x+1;i++) {
				int rez = Float.valueOf((y+i)/(x+i)*100).intValue();
	
				if(rez>z) {
					result = i;
					break;
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(result);
		System.out.println(sb);
	}

}

1. 입력 값 받기

2. 현재 승률 계산

3. 한판씩 진행하며 승률을 계산하고 1이 증가했을 때 멈춰서 출력

 

 

결과

=> 런타임에러(Runtime Error)

 

마지막 입력값을 넣었을 때 무한루프 발생

1000000000 470000000

 

 

 

[2차 풀이]

1. 정수로 계산하는 것이 더 정밀하기 때문에, int/long 타입으로 변경

2. 이분탐색으로 변경 -> 메모리초과/ 무한루프 문제 해결

3. 계산방식도 변경(정수형 연산으로)

승률 계산

전 (y  / x) * 100

후 (y * 100)/x

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

public class Ex1072 {

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

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

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

        long x = Long.parseLong(st.nextToken());
        long y = Long.parseLong(st.nextToken());

        int z = (int) ((y * 100) / x);  // 현재 승률
        int result = -1;

        if (z >= 99) {  // 승률이 99% 이상이면 변화 없음
            result = -1;
        } else {
            long low = 0, high = x;
            while (low <= high) {
                long mid = (low + high) / 2;
                int newZ = (int) (((y + mid) * 100) / (x + mid));

                if (newZ > z) {
                    result = (int) mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }

        System.out.println(result);
    }
}

 

 

결론)

x의 최대값이 10억인데, 컴퓨터 연산은 1억번 연산하는 데 약 1초이고, 최대 10억번을 실행한다고 하면 연산에 걸리는 시간은 총 10초이다.

여기 문제에서 주어진 시간은 2초였기 때문에 시간을 고려해야했다.

 

이때, 이분 탐색을 하면 몇 번 검색을 안해도 빠르게 search할 수 있다.

시간복잡도가 O(N)일 때, 이분 탐색의 시간복잡도는 O(logN) 이다.

 

무작정 풀기보다는 시간복잡도도 고려해서 나은 해결책을 찾아가도록 해야겠다.