1 - 1. Binary Search 예제 (백준 1072번: 게임)

백준 1072(게임)

이분 탐색의 예제로 풀어볼 문제입니다.

실제로 이분 탐색을 대상으로 문제가 나오기보단 대부분 Parametric Search 형태로 문제가 출제됩니다.

해당 문제는 Parametric Search로 보시는게 맞다고 생각합니다만, 좀 더 개념확립이 된다면 이 둘에 대한 차이에 대해서도 포스팅을 진행하겠습니다.

정답율이 꽤 낮은편인데도 불구하고 문제해결 아이디어는 생각보다 잘 떠오른 편이라 이 문제를 가져왔습니다.

사실 문제 자체가 분류가 안되어있다면, 이분 탐색이 익숙치 않다면 조금 헤맬 수 있는 문제라서 마냥 쉽다고 보긴 어려울 것 같습니다.

우선 아래의 두 조건에 대해 생각해 볼게요.

조건 1

앞으로의 모든 게임에서 지지 않는다

1. 지지 않는 다는 것은 '이기는 것만 고려한다.'라는 뜻입니다.

2. 만약 이 조건이 없었다면, 이기는 경우, 지는 경우 모두 고려했어야 했겠죠.

3. 결국 주어진 X에서 어떤 값(판수)을 더한다면 Y에도 같은 값을 더하면 된다는 얘기입니다.

조건 3

형택이가 게임을 몇 판 더해야 Z가 변하는지 구하는 프로그램

1. '몇판을 더 해야 Z가 변하는가?' 저는 이 조건이 조금 애매하다 생각하지만, 승률이 바뀔 수 있는 최소 판수를 구하라고 이해했습니다.
2. 즉, 위의 조건 1과 함께 지지 않으면서  승률이 바뀌는 경우: 승률을 올릴 수 있는 최소 판수를 찾으라는 의미입니다.
3. 만약 조건 1이 없었다면, 승률이 떨어지는 경우와 오르는 경우 두가지로 나누어 풀고 그때의 최솟값을 찾았어야 하겠죠.

이렇게 정리를 했는데, 이제 여기서 이분 탐색을 어떻게 적용할지 고민해 보셔야합니다.

1. 정렬 할 것이 존재하는가?

마땅히 없죠? 입력도 2개만 들어오구요.

2. 이미 정렬된 고정된 데이터가 존재하는가?

여기선 고정으로 1 ~ 10억까지 판수가 주어지고, 또한 승률도 0 ~ 100% 까지 존재합니다.

그럼 둘중 하나를 써서 탐색을 시작하면 될 것 같은데 어떤 값을 이용하는 것이 적절할까요.

사실 승률은 판수에 따라 계속 변동되기 때문에 판수를 통해 찾아보는게 편할 것 같아요.

또한, 소수점은 버린다 했으므로, 주어진 초기 승률이 Z라면 우리는 승률을 (Z + 1)로 만들어주는 추가 판수를 구해 결과로 뽑아야합니다.

따라서 저는 이전 설명때와 같이 비교할 값: target = Z(현재 승률)로 잡았습니다.

그런데 입력 X, Y에 좀 더 주의 하셔야 할 것이 앞으로 해야할 판수에 대해서 나온것이 없습니다.

입력으로 주어진 것은 이미 이제까지 했던 판수와 승리 횟수죠. 그리고 이는 최대 10억까지 들어옵니다.

앞으로 해야할 판수(승리 횟수) ?

최악의 경우에서 생각해 볼게요.

만약 형택이가 10억판을 했고, 그중 1승을 했다고 가정하면, 그때 승률은 0.000000001 -> 즉, 이 문제에 따르면 0% 입니다.

이때 승률을 올리기위한 판수는 얼마나 필요할까요?

모르긴 몰라도, 적어도 10억판을 해서 모두 이긴다면 승률이 50%까지 올라갑니다.

이렇게 직관적으로 보고 10억판을 했다고 가정해도 이분 탐색을 적용하면 시간 복잡도: logn= 대략 30ms 입니다.

저는 사실 이렇게 풀긴 했는데, 이게 과연 승률을 올릴 수 있는 판수의 범위가 적절한지 확인해보는 작업이 필요할 것 같아요.

만약 N판을 했는데 승률이 안올라 -1을 출력 했는데, (N + 1)판 만에 승률이 올랐다면 이는 잘못된 답이겠죠.

기본적으로 승률은 승과 패가 차지하는 비율에 따라 결정이 됩니다.

근데 이 승률에서 승리만 쟁취 했다고 가정한다면, 과연 어느 정도의 값이 필요한지 알아봅시다.

---

전체 시행 수 = X

이긴 횟수 = Y

진 횟수 = X - Y

승률 = Y / X

이때 Y, X는 미지수이므로 두가지로 나누어서 계산합니다.

우선 무승부는 없으니까 1) 이긴 횟수가 많은 경우, 2) 진 횟수가 많은 경우로 나누어 볼게요.

1) 이긴 횟수가 많은 경우: X > Y > (X - Y)

여기서 X 시행을 더 하고 모두 이겼다고 가정 하면: 2X > (X + Y) > (X - Y)

이때 승률은 (X + Y) / 2X 가 됩니다.

 이전              현재

이제 (Y / X) < (X + Y) / 2X 이 식이 성립하는지만 증명하면 되겠네요.

그러므로 좌변을 우변과 같은 모양으로 만들어서 (X + Y) / 2X = t로 치환해 보겠습니다.

이때, Y < X 이므로 t는 0.5보다 크고 1보다 작은 소수입니다.

(t가 0.5 보다 큰 것은 분모가 2X 이고 분자는 X + Y 이므로 자명합니다.)

좌변에 부모, 분자에 모두 2를 곱하고, 1을 더하고 빼서 좌변을 2(X + Y) / 2X - 1로 바꿔줍니다.

이제 양변의 값을 t로 치환하면  2t - 1 < t 이고, 1을 우항으로 넘기면  2t < t + 1

이때 양변을 t로 나눠주면 2 < 1 + (1 / t) 인데, t가 0.5 ~ 1 사이 소수였으니, 당연히 (1 / t) > 1 이고, 따라서 성립합니다.

그리고 이 값을 직접적으로 보면 2 < (2.5 보다크고 3보다 작은 수) 이므로 적어도 0.5는 증가했습니다.

2) 진 횟수가 많은 경우 X > (X - Y) > Y

이도 위와 같이 적용해주면: 2X > (2X - Y) > X + Y

이때 승률은 위와 동일합니다. (X + Y / 2X)

이전             현재

여기서도 (Y / X) < (X + Y / 2X) 똑같이 성립되는지 증명해 볼게요.

이 식도 똑같이 좌변을 우변과 같은 모양으로 만들어서 (X + Y) / 2X = t로 치환해 보겠습니다.

이 식에서도 마찬가지로 Y < X 라는 것은 변함이 없습니다.

결국 굳이 안해봐도 우리가 증명해야할 식과 거기에 포함된 조건식 두개가 모두 같으니 성립하게 됩니다.

이렇게 X회 게임을 더 한 경우 

이전 게임보다 못해도 계산 값이 0.5 이상 커진다는 것이 증명이 되었으니, 이는 적어도 승률이 50%는 오른다는 이야기이죠.

---

사실 뭐 이보다 더 나은 값이 있지 않을까 싶긴한데.. 제 능력 밖인거 같아요. ㅎㅎ

아무튼 증명도 되었으니 코드를 짜봅시다.

기본적인 동작은 이분 탐색만 실시하고 탐색 중간에 승률을 뽑아주는 메소드를 생성해서 계속 비교했습니다.

이 메소드는 getWinRate 라고 이름 지었구요.

소수점 자리는 무시한다 했으므로 Y(승리 횟수) * 100 / X (게임 판수)를 반환하게 했습니다.

원래 식은 Y / X * 100 인데, 이렇게 계산하면 Y는 항상 X보단 작게 되잖아요.

그래서 0이라는 결과를 반환하기 때문에 저런식으로 처리했습니다.

또한 Y가 최대 10억이고 100을 곱하면 int 범위를 초과하므로 마음 편하게 그냥 모두 long으로 잡아주었습니다.

우선 이분 탐색 메소드 부터 보여드리겠습니다.

1072번 Binary Search 메소드

private static int binarySearch(long x, long y, long target) {
    int start = 1, end = (int) x, result = 0;
    if(getWinRate(x + x, y + x) == target) return -1;        // 승률이 안오르는 경우
        
    while(start <= end) {
        int mid = (start + end) / 2;
        long z = getWinRate(x + mid, y + mid);        // 승률이 오른건지 체크
            
        if(z > target) {
            end = mid - 1;
            result = mid;
        }
        else {
            start = mid + 1;
        }
        
        return result;
    }
}

기본 동작은 이전에 했던 이분 탐색 알고리즘과 똑같은데 하나 차이가 있다면  'z <= target' 의 경우는 같이 묶어줬습니다.

어차피 승률이 작아지거나 같은 경우는 우리가 원하는 방향이 아니니까요.

그러한 경우엔 판수를 더 늘려 줬구요. 승률이 커지는 경우에만 판수를 줄여가면서 그때 해당한 최소 판수를 저장해주었습니다.

그리고 아까 이제까지 시행한 횟수 x 만큼만 더해도 50%은 족히 올랐는데, 그래도 안오르는 경우가 있을거에요.

승률이 소수점을 무시한다 했으니까요.

예를 들면 99%의 승률을 가진다면 어떻게해도 100%는 만들 수 없으니 그런 경우는 탐색전에 미리 현재 승률과 비교해서 안올랐다면 -1을 반환했습니다.

1072번 getWinRate 메소드

private static long getWinRate(long x, long y) {
    return y * 100 / x;
}

승률 계산 메소드는 위에서 설명 드린것과 동일하게 입력했습니다.

Boj1072.java 전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
/**
 * 
 *     @author minchoba
 *    백준 1072번: 게임
 *
 *    @see https://www.acmicpc.net/problem/1072/
 *
 */
public class Boj1072 {    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long X = Integer.parseInt(st.nextToken());
        long Y = Integer.parseInt(st.nextToken());
        
        long winRate = getWinRate(X, Y);
        System.out.println(binarySearch(X, Y, winRate));
    }
    
    private static int binarySearch(long x, long y, long target) {
        int start = 1, end = (int) x, result = 0;
        if(getWinRate(x + x, y + x) == target) return -1;        // 승률이 안오르는 경우
        
        while(start <= end) {
            int mid = (start + end) / 2;
            long z = getWinRate(x + mid, y + mid);        // 승률이 오른건지 체크
            
            if(z > target) {
                end = mid - 1;
                result = mid;
            }
            else {
                start = mid + 1;
            }
        }
        
        return result;
    }
    
    private static long getWinRate(long x, long y) {
        return y * 100 / x;                        // 소수화 방지
    }
}
 

채점 결과

아래 제출은 원래 제가 처음에 증명하기전에 쓴 탐색 범위를 무조건 +10억으로 하고 나온 결과입니다.

시간 복잡도 자체가 작기 때문에 결과에서도 별 차이가 없네요.

이해안가는 것이나, 질문 또는 잘못된 부분은 댓글로 지적 부탁드려요. 감사합니다.

문제의 저작권은 백준 온라인 저지에 있습니다.