[BAEKJOON] 1072 게임

문제 요약

• 알고리즘 분류: 이진 탐색, 수학
• 난이도: Silver3
• 문제내용:
  • X: 게임 횟수, Y: 이긴 횟수, Z: 승률(정수)
  • 계속 이긴다고 가정 했을때 몇판 더해야 승률이 변하는지 구하여라 만약 변하지 못하면 -1로 반환 하여라

• 사이트: https://www.acmicpc.net/problem/1072

 

문제풀이

 이번 문제는 하나씩 +1 씩 대입해서 정답은 나오지만 최대 숫자가 100억이다. 그리고 승률은 소수가 아닌 정수이다. 그럼 변화할라면 1%올라가야 하는데 1000억기준으로 올라갈라면 최대 10억번을 탐색 해야 한다. 그럼 초당 연산 1억기준으로 O(N)탐색 하면 오류가 날수 있다. 그래서  O(logN)탐색 시간초과 이내로 끝내야 통과가 된다. 그래서 이진탐색으로 해결할것이다. 이진탐색에 대한 내용은 아래에 대한 글로 확인 하면된다.

https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89

이진 탐색

 

문제 접근 방법

 어떻게 이진 탐색으로 풀것이라면 0 부터 X까지 lower bound방식으로 진행할것이다. 그럼 어떻게 최소한 이긴횟수로 확률 1%올릴것인가 보면 왼쪽을 0 오른쪽을 X크기만큼 범위를 지정 하고 X / 2만큼 mid로 설정 한뒤로 할것이다.

그 다음 Rate를 아래와 같이 계산 한 후 Z와 비교 할것이다. 그리고 Rate와 Z비교 하면 end를 mid까지 내리고 반대면 start를 mid까지 올린후 다시 이진 탐색한다. 이진탐색은 답이 정해진것이 아니라 최소한 이긴 회수 증가 하는것을 구해야 하기 때문에 start와 end가 같을때 까지 탐색 하면된다.

이렇게 설명하면 이해가 안될수 있어서 백준 4번 예제 하나 가지고 설명 할것이다.

1. 0 ~ 99000가 주어지고 Z는 0프로이다. 그럼 최소한 1프로 올리는것을 찾아야 한다.
2. start = 0, end = 99000, mid = 49500로 지정 하고 Rate를 구한다.
Rate = (0 + 49500) * 100 / (99000 + 49,500) = 33
Z랑 비교 하면 크다 그래서 end를 mid - 1로 지정한다. 그럼 end는 49499 된다.
3. start = 0, end = 49499, mid = 24,749
Rate = (0 + 24749) * 100 / (99000 + 24749) = 19
Z랑 비교 하면 크다 그래서 end를 mid - 1로 지정한다. 그럼 end는 24748 된다.
4. start = 0, end = 24748, mid = 12374
Rate = (0 + 12374) * 100 / (99000 + 12374) = 11
Z랑 비교 하면 크다 그래서 end를 mid - 1로 지정한다. 그럼 end는 12373 된다.
5. start = 0, end = 12373, mid = 6186
Rate = (0 + 6186) * 100 / (99000 + 6186) = 5
Z랑 비교 하면 크다 그래서 end를 mid - 1로 지정한다. 그럼 end는 6187 된다.
6.start = 0, end = 6187, mid = 3093
Rate = (0 + 3093) * 100 / (99000 + 3093) = 3
Z랑 비교 하면 크다 그래서 end를 mid - 1로 지정한다. 그럼 end는 3092 된다.
7.start = 0, end = 3092, mid = 3093
Rate = (0 + 1546) * 100 / (99000 + 1546) = 1
Z랑 비교 하면 크다 그래서 end를 mid - 1로 지정한다. 그럼 end는 1545 된다.
8.start = 0, end = 1545, mid = 772
Rate = (0 + 772) * 100 / (99000 + 772) = 0
Z랑 비교 하면 같다 그래서 start를 mid + 1로 지정한다. 그럼 start는 773 된다.
9.start = 773, end = 1545, mid = 1159
Rate = (0 + 1159) * 100 / (99000 + 1159) = 1
Z랑 비교 하면 크다 그래서 end를 mid - 1로 지정한다. 그럼 end는 1159 된다.
10.start = 773, end = 1159, mid = 966
Rate = (0 + 966) * 100 / (99000 + 966) = 0
Z랑 비교 하면 같다 그래서 start를 mid + 1로 지정한다. 그럼 start는 967 된다.
11.start = 967, end = 1159, mid = 1063
Rate = (0 + 1063) * 100 / (99000 + 1063) = 1
Z랑 비교 하면 크다 그래서 end를 mid - 1로 지정한다. 그럼 end는 1062 된다.
12.start = 967, end = 1062, mid = 1014
Rate = (0 + 1014) * 100 / (99000 + 1014) = 1
Z랑 비교 하면 크다 그래서 end를 mid - 1로 지정한다. 그럼 end는 1013 된다.
13.start = 967, end = 1013, mid = 990
Rate = (0 + 990) * 100 / (99000 + 990) = 0
Z랑 비교 하면 같다 그래서 start를 mid + 1로 지정한다. 그럼 start는 991 된다.
14.start = 991, end = 1013, mid = 1002
Rate = (0 + 1002) * 100 / (99000 + 1002) = 1
Z랑 비교 하면 크다 그래서 end를 mid - 1로 지정한다. 그럼 end는 1001 된다.
15.start = 991, end = 1001, mid = 996
Rate = (0 + 996) * 100 / (99000 + 996) = 0
Z랑 비교 하면 같다 그래서 start를 mid + 1로 지정한다. 그럼 start는 997 된다.
16.start = 997, end = 1001, mid = 999
Rate = (0 + 999) * 100 / (99000 + 999) = 0
Z랑 비교 하면 같다 그래서 start를 mid + 1로 지정한다. 그럼 start는 1000 된다.
17.start = 1000, end = 1001, mid = 1000
Rate = (0 + 1000) * 100 / (99000 + 1000) = 1
Z랑 비교 하면 크다 그래서 end를 mid - 1로 지정한다. 그럼 end는 999 된다.
18 start보다 end가 작다. 그럼 mid를 결과 값을 반환 한다. 그럼 답은 1000이된다.

예제를 보면 18딘계 만으로 최소한으로 찾아 낼수 있다.

마무리

 위와 같이 구현했을때 시간 복잡도는 O(logN)만큼 나온다. 

이번문제에서는 내가 놓친 부분은 아래와 같다.

1. 최대 숫자가 1000억인것 인지 못한채로 브루드 탐색으로 풀었다.
2. Z가 99퍼 이상일때 변화 못한다것은 확인 못했다
3. 탐색 bound를 X-Y만큼 오류가 났는데 X만큼 해야 bound안에 든다.

 

Code

 자바는 / 연산하면 정수 / 정수 = 정수로 나오지만 파이썬  정수 / 정수 = 실수로 계산 되기 때문에  //로 처리해야한다.

Python

X, Y = map(int, input().split())
Z = Y * 100 // X
start, end = 0, X
result = X #결과

# 이분탐색
# 확율 올라가는것이 최소 될때까지 탐색
while start <= end:

    mid = (start + end) // 2
    # 이긴 횟수 증가후 승률
    nowRate = (Y + mid) * 100 // (X + mid)
    # nowRate가 Z보다 크면 end값을 줄인다.
    if(nowRate > Z):
        result = mid
        end = mid - 1
    else:
        start = mid + 1

print(result if Z < 99 else -1)

Java

범위가 최소 1000억이라서 Integer 타입으로 범위가 안되기 때문에 Long으로 해야 한다.

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 범위가 Integer 넘어서 Long 타입으로 해야함
        long X = Long.parseLong(st.nextToken());
        long Y = Long.parseLong(st.nextToken());
        long Z = Y * 100 / X;

        long start = 0;
        long end = X;

        long nowRate; // 이긴 횟수 증가후 승률
        long result = X;// 결과
        // 이분탐색
        // 확율 올라가는것이 최소 될때까지 탐색
        while (start <= end) {
            long mid = (start + end) / 2;
            nowRate = (Y + mid) * 100 / (X + mid);
            // nowRate가 Z보다 크면 end값을 줄인다.
            if(nowRate > Z){
                end = mid - 1;
                result = mid;
            }else{
                start = mid + 1;
            }
            //System.out.println("Start: " + start + ", End: " + end + ", MID: " + mid + ", Rate: " + nowRate);
        }
        // Z가 99퍼이면 더이상 올라갈수 없음
        System.out.println(Z >= 99? -1 : result);

	}

}