백준 이분탐색 문제들 (1072 게임, 1654 랜선자르기, 1920 수찾기, 2512 예산)

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

1072번: 게임

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

z = int(100 * y / x)

if z >= 99:
    print(-1)
else:
    ans = 0
    start = 0
    end = 1000000000
    while(start <= end):
        mid = (start + end) // 2
        if int(100 * (y + mid) / (x + mid)) <= z:
            start = mid + 1
        else:
            end = mid - 1
    print(end + 1)

---

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

1654번: 랜선 자르기

# 랜선의 길이 구하기
# 랜선의 길이 움직여 랜선 개수 채우는지 보기

k, n = map(int, input().split())
lan = [int(input()) for _ in range(k)]

start = 1
end = max(lan)

while(start <= end):
    mid = (start + end) // 2
    count = 0
    for i in lan:
        count += (i // mid)
    if count >= n:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)

---

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

1920번: 수 찾기

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))

a.sort()
result = []

for i in b:
    start = 0
    end = n - 1
    flag = 0
    while(start <= end):
        mid = (start + end) // 2
        if i < a[mid]:
            end = mid - 1
        elif i > a[mid]:
            start = mid + 1
        elif i == a[mid]:
            flag = 1
            break
    result.append(flag)

for i in result:
    print(i)

이 문제는 해시로도 해결가능하다. 검색이 용이한 해시!

import sys 
input = sys.stdin.readline

n = map(int, input()) 
a = list(map(int, input().split())) 

pool = {} 
for k in a: 
    pool[k] = 1 

m = map(int, input()) 
b = list(map(int, input().split())) 
for t in b: 
    if t in pool:
        print(1) 
    else: 
        print(0)

---

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

2512번: 예산

import sys
input = sys.stdin.readline

n = int(input())
bud = list(map(int, input().split()))
m = int(input())

start = 1
end = max(bud)

while(start <= end):
    count = 0
    mid = (start + end) // 2
    for i in bud:
        if i <= mid:
            count += i
        else:
            count += mid
    if count <= m:
        start = mid + 1
    else:
        end = mid - 1

print(end)