이분탐색 올바른 사고 연습하기 1편

1. 문제1

 

1072번: 게임 (acmicpc.net)

1072번: 게임

 

2. 풀이1

 

탐색범위는 x+1부터 충분히 큰 수까지..

 

x가 제한이 10의 9제곱인데.. 이는 입력으로 주어지는 x가 10의 9제곱이지 가능한 제한이 10의 9제곱이라는 뜻은 아니다.

 

그래서 대충 10의 18제곱까지 탐색하도록 범위를 잡았다

 

그리고 절대로 지지 않는다고 했기 때문에... x 기준으로 현재 x+k를 잡았다면... 

 

y값은 y+k로 바뀌겠지

 

그리고 그때 변화된 승률도 (y+k)*100//(x+k)

 

문제에서 요구하는건 승률이 변하냐 안변하냐이다.

 

그러니까 새롭게 계산한 승률 (y+k)*100//(x+k)와 원래 승률 y*100//x가 서로 다른지 같은지를 체크한다.

 

서로 다르다면? 

 

문제에서 요구하는건 승률이 변하는 "최소 판수"이므로.. end = mid로 옮겨서 더 작은 판수가 가능한지 체크

 

서로 같다면?

 

현재 정한 판수보다 큰 판수를 탐색해야할테니, start = mid + 1로 옮긴다

 

from sys import stdin

def binary_search(target,start,end,x,y):
    
    while start < end:
        
        mid = start + (end-start)//2

        new_y = y + mid-x

        new_z = new_y*100//mid

        if new_z != target:
            
            end = mid
        
        else:
            
            start = mid + 1
    
    return end

MAX = 10**18

x,y = map(int,stdin.readline().split())

z = y*100//x

answer = binary_search(z,x+1,MAX+1,x,y)

if answer > MAX:
    
    print(-1)

else:
    
    print(answer - x)

 

탐색한 결과가.. 최대 범위로 지정한 값보다 크게 나온다면.. 아무리 해도 승률이 변하지 않는다는 의미니까 -1을 출력했고

 

그 이외의 경우는 나온 결과 - 원래 판수를 하면 최소 해야하는 판수가 되겠지

 

 

3. 풀이2

 

근데 그냥 일차부등식으로도 풀린다고 한다

 

앞으로 게임에서 반드시 승리하므로, 승률은 무조건 증가할것이다.

 

이때, Z가 정수이므로, Z가 최소로 변한다면...

 

Z가 1 증가하는 것이고 최소 k판 더 한다고 하면, 그 승률은 $\frac{100y+100k}{x+k}$

 

원래 승률은 $z = \frac{100y}{x}$

 

따라서 다음 부등식을 만족해야한다.

 

$$\frac{100y+100k}{x+k} >= z+1$$

 

부등식을 정리하면... $100y+100k >= x(z+1) + k(z+1)$ 여기서 이항해서 더 정리하면...

 

$$100y - x(z+1) >= k(z -99)$$

 

이 부등식에서 z = 99이면 성립하지 않으므로, z가 변하지 않는 경우이고

 

z = 100이면, $100y-100x >= k$인데, 좌변이 음수이므로 k가 음수가 되니 성립하는 식이 아니다. 

 

그래서 z >= 99이면 몇판을 해도 변하지 않는다

 

반대로 z < 99이면, z-99로 부등식의 양변을 나눠서...

 

$$(100y-x(z+1))(z-99) <= k$$

 

따라서 좌변의 식을 계산해서 최소 정수 k를 구해주면 되겠다

 

from sys import stdin

x,y = map(int,stdin.readline().split())

z = 100*y//x

if z >= 99:
    
    print(-1)

else:

    k = (100*y-x*(z+1))/(z-99)

    if k == int(k):
        
        print(int(k))
    
    else:

        print(int(k)+1)

 

 

 

4. 문제2

 

7795번: 먹을 것인가 먹힐 것인가 (acmicpc.net)

7795번: 먹을 것인가 먹힐 것인가

 

 

5. 풀이

 

핵심은 (A,B) 쌍의 개수를 셀건데, A > B인 쌍의 개수만 셀것이다

 

A,B 배열을 정렬하고, A를 target으로 잡은 다음에 B 배열에서 B[mid]가 target보다 크거나 같다면??

 

mid이후는 target보다 모두 크거나 같다.. 그러니까 볼 필요가 없으므로 end = mid로 옮겨준다. 왜냐하면 B < A인 쌍을 구해야하니까... 

 

이러한 지점은 mid보다 작은 지점에 있을 것이다

 

반대로 B[mid] < target이라면?  mid이후는 조건을 만족하는 부분이다.. 그러면 start = mid + 1???

 

근데 mid도 조건을 만족할 수 있는데...?

 

from sys import stdin

def binary_search(array,target,start,end):
    
    while start < end:
        
        mid = start + (end - start)//2

        if array[mid] > target:
            
            end = mid 
        
        else:
            
            start = mid + 1
    
    return end
            
T = int(stdin.readline())

for _ in range(T):
    
    n,m = map(int,stdin.readline().split())

    A = list(map(int,stdin.readline().split()))

    B = list(map(int,stdin.readline().split()))

    A.sort()
    B.sort()

    count = 0

    for i in range(m):
        
        j = binary_search(A,B[i],0,n)

        if j == n:
            
            j -= 1
            break

        count += (n-(j+1)+1)

    print(count)

 

이렇게 생각이 꼬이더니.. 반대로 B를 target으로 잡은 다음에 A배열에서 이분탐색을 해보자는 생각에 이르렀다

 

A배열에서 target = B[i]보다 큰 지점을 이분탐색으로 찾는다면...

 

A[mid] > target이라면.. mid 이후는 조건을 만족하는 부분이므로.. end = mid로 해서 mid 보다 작은 쪽을 탐색해야 할 것이다.

 

반대로 A[mid] <= target이면... mid 이전은 모두 target보다 작으니 start = mid + 1로 해서 mid보다 큰 쪽을 탐색해야 한다.

 

이렇게 하면 A를 target으로 잡아 B 배열에서 이분탐색할때 꼬이던 로직이 명확해진다..

 

이분 탐색한 결과 end를 return하고 그 지점이 j라면.. j 이후는 모두 A > B인 지점이다 

 

따라서, A배열의 개수 - (j+1) + 1을 해서 j부터 A배열 끝까지 개수를 세주면.. B가 고정되어 있을때, A > B인 쌍을 셀 수 있다.

 

A > B를 만족하는 값이 A배열에 존재하지 않아 j = n이 된다면... 반복문을 탈출해준다.

 

현재 B[i]에서 A > B인 쌍을 찾지 못했다면.. 모든 A의 원소에 대해 B[i]보다 작다는 뜻이고.. 현재 A,B가 정렬되어 있으므로

 

B[i]보다 큰 B[i+1]도 당연히 모든 A의 원소보다 크므로, 그 이후는 A > B인 쌍이 존재하지 않는다